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

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;

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

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。