剑指 Offer 33. 二叉搜索树的后序遍历序列

题目

剑指 Offer 33. 二叉搜索树的后序遍历序列

我的思路

在二叉搜索树中后序遍历的特点是，最后一个数组元素对应的节点是树的根，同时可以把除最后一个元素以外前面的节点分成两段，一段都大于根，一段都小于根。递归检查这个特点

我的实现

class Solution {
public:
    bool result = true;
    void check(int left,int end,vector<int>& postorder){
        if(left>=end-1){
            return;
        }else{
            int pos = left;
            int m;
            while(postorder[pos]<postorder[end]){
                pos++;
            }
            m = pos;
            while(postorder[pos]>postorder[end]){
                pos++;
            }
            if(pos!=end){
                result =false;
            }else{
                check(left,m-1,postorder);
                check(m,end-1,postorder);
            }
        }
    }
    bool verifyPostorder(vector<int>& postorder) {
        check(0,postorder.size()-1,postorder);
        return result;

    }
};
/*
在二叉搜索树中后序遍历的特点是，最后一个数组元素对应的节点是树的根，同时可以把除最后一个元素以外前面的节点分成两段，一段都大于根，一段都小于根。递归检查这个特点
*/

时间复杂度最坏情况是n^2。

空间复杂度最坏情况是n，递归深度

拓展学习

官方题解的法二也不错，借助辅助空间时的复杂度降到了n。

利用了后序遍历的倒序是前序遍历的对称，所以当前元素若比前一个元素val大，那么当前元素一定是前一个元素对应节点的右孩子，如果比前一个元素小，那么一定是某个节点的左孩子，该双亲节点是比当前节点val大的val最小的节点。可以通过辅助空间栈存储这些潜在的双亲节点，因为如果当前节点之后的节点一定小于它对应的双亲节点！

class Solution:
    def verifyPostorder(self, postorder: [int]) -> bool:
        stack, root = [], float("+inf")
        for i in range(len(postorder) - 1, -1, -1):
            if postorder[i] > root: return False
            while(stack and postorder[i] < stack[-1]):
                root = stack.pop()
            stack.append(postorder[i])
        return True

作者：jyd
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。