当前位置：
  1. 首页
  2. 剑指offer刷题第二期
  3. 问题详情

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

本问题对应课程链接：剑指offer刷题第二期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路
2、给出时间和额外空间复杂度

shuaidi
253 35

共以下 35 个回答

  • 宁 永久会员 2023年3月13日 上午11:03

    把握特点，右侧元素比中间元素大

    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        //后序遍历： 左右中
        if(postorder == null || postorder.length == 0){
            return true;
        }
        return check(postorder, 0, postorder.length - 1);
    }
    public boolean check(int[] postorder, int start, int end){
        if(start >= end){
            return true;
        }
        int mid = postorder[end];
        int p = start;
        while(postorder[p] < mid) p++;
        for(int i = p; i < end; i ++){
            if(postorder[i] < mid){
                return false;
            }
        }
        return check(postorder, start, p - 1) && check(postorder, p, end - 1);
    }
}
    0 赞同 0 条回复
  • lucca 普通 2023年1月4日 下午5:00

    递归，分辨校验左子树和右子树有且只有一个，只需要保证大于和小于根节点的区间是连续的且只有一个即可

    • 时间复杂度O(N^2)，最坏情况，树退化成链表，每次递归遍历其前n个，递归n次
    • 空间复杂度O(N)
    0 赞同 0 条回复
  • cute. 普通 2023年1月2日 下午11:49 
    /**
 * @param {number[]} postorder
 * @return {boolean}
 */
 var verifyPostorder = function(postorder) {
  if(postorder.length <= 2)
      return true;
  // 后序遍历中最后一个元素为根节点
  let root = postorder[postorder.length - 1];
  // 寻找第一个大于根节点的元素，它为分界点，前面为左子树，后面为右子树
  let index = postorder.findIndex(item => item > root);
  // 进行分割
  let left = postorder.slice(0, index);
  let right = postorder.slice(index, postorder.length-1);
  if(Math.min(...right, root) !== root)
      return false;
  return verifyPostorder(left) && verifyPostorder(right);
};
    • 时间复杂度：O(n）
    • 空间复杂度：O(n)
    0 赞同 0 条回复
  • Gg 普通 2023年1月2日 下午4:55 
    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null){
            return true;
        }
        return verify(postorder,0,postorder.length - 1);
    }

    private boolean verify(int[] postorder, int begin, int end){
        if(begin >= end){
            return true;
        }
        int root = postorder[end];
        // 找到大于或等于根节点的节点，为右子树的开始
        int p = begin;
        while(postorder[p] < root){
            p++;
        }
        for(int i = p; i < end; i++){
            if(postorder[i] < root){
                return false;
            }
        }
        // 递归左右子树
        return verify(postorder,begin,p-1) && verify(postorder,p,end-1);
    }
}
    0 赞同 0 条回复
  • PatNick 普通 2022年12月26日 下午3:28 
    def verifyPostorder(postorder):

    if postorder == None:
        return True

    return find(postorder,0,len(postorder)-1)



def find(order,i,j):
    if i > j:
        return True

    root = order[j]
    p = i
    # 寻找order[：-1]中第一个大于root的位置
    while order[p] < root:
        p += 1

    for __ in order[p:j]:
        # 确保后面一部分所有节点不大于根结点
        if __ < root:
            return False

    return find(order,i,p-1) and find(order,p,j-1)
    0 赞同 0 条回复
  • 🚲南下 普通 2022年12月2日 上午11:25 
    class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        stack<int> s;
        // 初始化root为最大值，即 把根节点 看做 无穷大 的左孩子
        int root = INT_MAX;
        // 逆序遍历
        // 后序遍历的 左-右-根 --> 根-右-左
        for(int i = postorder.size() - 1; i >= 0; i--){
            // 如果 左子树节点大于其根节点
            // 则 不满足二叉搜索树的定义
            if(postorder[i] > root){
                return false;
            }
            // 如果 栈非空 且 当前遍历节点小于栈顶节点
            // 则需要 在前面栈中的元素找到其父节点 并更新 root
            while(!s.empty() && postorder[i] < s.top()){
                root = s.top();
                s.pop();
            }
            s.push(postorder[i]);
        }
        return true;
    }
};
    0 赞同 0 条回复
  • Tolkien 永久会员 2022年11月18日 下午2:53 
    /**
     * 辅助栈
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public boolean verifyPostorder(int[] postorder) {
        // 1. 由图可得，将数组倒序，若n大于上一个数字则n为上一个节点的右儿子
        // 若n小于上一个节点，它将回溯寻找比它小的节点，作为那个节点的左儿子

        // 2. 通过辅助栈来模拟以上操作
        // 倒序遍历数组将每一个节点入栈，使栈顶始终为上一个节点
        // 当前节点与栈顶比较，若栈顶小于当前节点，则直接将当前节点入栈
        // 若栈顶大于当前节点，则不断出栈，直到栈顶小于当前节点，再入栈

        // 3. 如何判断错误情况
        // 每个节点都小于其祖先节点的父节点，
        // 祖先节点定义为线索二叉树中某个结点的左节点，其右子树以及右子树的右子树...共享一个祖先节点

        Stack<Integer> stack = new Stack<>();
        int ancestor = Integer.MAX_VALUE;

        // 1. 倒序遍历数组
        for (int i = postorder.length-1; i >= 0; i--) {
            // 3. 判断错误情况
            if (ancestor < postorder[i]) {
                return false;
            }
            // 2. 辅助栈模拟操作
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                ancestor = stack.pop();
            }

            stack.push(postorder[i]);
        }

        return true;
    }
    0 赞同 0 条回复
  • xye 普通 2022年11月17日 下午9:10 
    //二叉搜索树的特征就是根节点的左子树都比其小，右子树都比其大
func verifyPostorder(postorder []int) bool {
    if len(postorder) == 0 {
        return true
    }
    return f(postorder, 0, len(postorder)-1)
}
//递归函数
func f(pos []int, i int, j int) bool {
    if i >= j {
        return true
    }
    root := pos[j]
    p := i
    for ;pos[p] < root; p++ {}
    for k := p; k < j ;k++ {
        if pos[k] <= root {
            return false
        }
    }
    return f(pos, i, p-1) && f(pos, p, j-1)

}

    时间O(N^2) 空间O(N)

    0 赞同 0 条回复
  • 浅夏的无奈 普通 2022年11月12日 下午11:52

    //时间复杂度 O(n^2)
    //空间复杂度 O(n)

    //时间复杂度 O(n^2)
//空间复杂度 O(n)

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer> stack =new Stack<>();
        int root = Integer.MAX_VALUE;
        //从数组找到根节点的数，向前遍历
        for(int i=postorder.length-1;i>=0;i--){
            //判断是否符合二叉搜索树的规则
            if(postorder[i] > root) return false;
            //寻找当前节点的父节点
            while(!stack.isEmpty()&&stack.peek() > postorder[i]){
                root = stack.pop();
            }
            //添加节点入栈
            stack.add(postorder[i]);
        }
        return true;
    }
}
    0 赞同 0 条回复
  • symbol 普通 2022年11月11日 上午12:56 
    func verifyPostorder(postorder []int) bool {
    //数组为空了
    if len(postorder) < 1 {
        return true
    }
    temp := postorder[len(postorder)-1] //根节点值
    //数组中第一个比根节点大的值及其后面的值为右子树
    index :=len(postorder)-1// 第一个大于根节点值的下标，初始值设为根节点下标
    for i,v := range postorder {
        if v > temp{
            index = i
            break
        }
    }
    //左子树
    left := postorder[:index]
    //右子树
    right := postorder[index:len(postorder)-1]
    //若右子树中有比根节点小的 则不是二叉搜索树的后序遍历
    for j :=0;j< len(right);j++{
        if right[j] < temp{
            return false
        }
    }
    //再去判断左右子树是不是
    return verifyPostorder(left)&&verifyPostorder(right)
}
    0 赞同 0 条回复
  • 黎昕 普通 2022年11月8日 下午9:53

    解法一：递归+分治
    序列最后的元素为root，从头至尾找到第一个大于root的元素right，如果从right到root之间存在小于root的元素，返回flase
    否则从right左右两边分为两个子树进行判断。

    class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        def recur(leftindex,rootindex)->bool:
            # leftindex为当前子树的左下标，rootindex为根下标
            # 递归基
            if leftindex>=rootindex:
                return True
            # 递归
            for i in range(leftindex,rootindex+1):
                # 找到第一个大于等于root的节点值所在index range函数是左闭右开的
                if postorder[i]>=postorder[rootindex]:
                    break;
            if i+1>=rootindex:
                return recur(leftindex,i-1)
            else:
                for j in range(i,rootindex):
                    if postorder[j]<postorder[rootindex]:
                        return False
                return recur(leftindex,i-1) and recur(i,rootindex-1)

        return recur(0,len(postorder)-1)

    解法二：单调栈
    后序遍历为 左右中，其逆序是 中右左
    这种逆序的遍历形象上很像是一种将树从右斜方从左上到右下一行行遍历的结果
    如果栈空或者栈顶元素大于当前遍历的元素，压栈（说明是右子树），如果小于，弹栈直到栈顶元素大于遍历元素，最后一次弹出的元素就是当前元素的父节点（给parent存下来），在之后压栈中（因为前面进行弹栈操作了，所以右子树肯定是没有了，所以后面的元素不可能大于当前的parent值），一旦出现大于parent的值，就是错的。
    根据上面的分析，最开始的parent需要默认设为int最大值，这样就可以将root节点的处理也包括进去了，不用特殊处理

    class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        # postorder=postorder[::-1]
        stack=[]
        parent=sys.maxsize
        for i in range(len(postorder)-1,-1,-1):
            while stack and postorder[i]<stack[len(stack)-1]:
                parent=stack.pop()
            if parent<postorder[i]:
                return False
            stack.append(postorder[i])
        return True
    0 赞同 0 条回复
  • 小肸 永久会员 2022年11月8日 上午11:03

    第一种思路：根据二叉搜索树的特点和后序遍历的顺序。递归分治的思路。数组的最后一个元素就是根节点，找到大于根节点第一个值，在这个值之前的所有元素都小于这个值，在这个值之后的所有元素都大于这个值，这颗树就是二叉搜索树，再递归的判断左子树和右子树是不是二叉搜索树。时间复杂度最坏情况下是O(N^2)，空间复杂度为O（N）。

    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return verifyPostorderCore(postorder, 0, postorder.length - 1);
    }
    private boolean verifyPostorderCore(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int index = left;
        while (postorder[index] < postorder[right]) {
            index ++;
        }
        int mid = index; // 记录第一个比根节点大的元素下标
        while (postorder[index] > postorder[right]) {
            index ++;
        }
        return index == right && verifyPostorderCore(postorder, left, mid - 1) && verifyPostorderCore(postorder, mid, right - 1);
    }
}

    第二种思路：单调栈。可是二叉搜索树的值顺序为右>中>左，后序遍历的顺序为左右中，没有单调性。可是后序遍历的逆序是中右左。有一定的单调性。时间和空间复杂度都为O(N)。

    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> stack = new LinkedList<>();
        int e = Integer.MAX_VALUE;
        // 逆向遍历， 后序遍历的逆序: 中 右 左， 值应该越来越大，当值变小时，说明开始进入左子树， 值应该单调递减
        for (int i = postorder.length - 1; i >= 0; i --) {
            if (postorder[i] > e) {
                return false;
            }
            while (!stack.isEmpty() && postorder[i] < stack.peek()) {
                e = stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}
    0 赞同 0 条回复
  • 刺猬 普通 2022年11月7日 下午12:32 
    class Solution {
public:
    bool verifyPostorder(vector& postorder) {
        return recur(postorder, 0, postorder.size() - 1);
    }
    bool recur(vector& postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder.at(p) < postorder.at(j)) p++;
        int m = p;
        while(postorder.at(p) > postorder.at(j)) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
};

    时间复杂度O(N^2)
    空间复杂度O(N)

    0 赞同 0 条回复
  • 酥合 普通 2022年11月6日 下午9:37 
    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }

    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while(postorder[p] > postorder[j]) p++;
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}

    时间复杂度：O(n ^ 2)
    空间复杂度：O(n)

    0 赞同 0 条回复
  • @ 普通 2022年11月6日 下午5:20

    思路：依次找这这棵数的左子树、右子树、根节点，并判断他们的顺序是否正确，如果正确，再进行子递归，继续重复判断
    时间复杂度：O(N^2)
    空间复杂度：O(N)

    class Solution {
    public boolean verifyPostorder(int[] postorder) {

        return rec(postorder, 0, postorder.length - 1);

    }

    public boolean rec(int[] postorder, int l, int r) {
        if (l >= r)
            return true;

        int p = l;

        //根节点
        int root = postorder[r];

        //[l,mid - 1]为左子树
        while (postorder[p] < root)
            p++;


        int mid = p;

        //[mid,j - 1]为右子子树
        while(postorder[p] > root)
            p++;

        //如果p != j ，则说明在右子树中找到了比根节点还要小的值，这不符合二分搜索树的性质。
        return p == r && rec(postorder, l, mid - 1) && rec(postorder, mid, r - 1);
    }
}
    0 赞同 0 条回复
  • lobort 普通 2022年11月5日 下午3:09 
    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null){
            return true;
        }
        return func(postorder, 0, postorder.length-1);
    }

    //判断左右子树是不是搜说二叉树
    public boolean func(int[] postorder, int i, int j){
        if(i >= j){
            return true;
        }
        //后续遍历的最后一个数是根节点
        int root = postorder[j];
        int cur = i; 
        //找到第一个大于根节点的数的下标 标记为cur
        while(postorder[cur] < root){
            cur++;
        }
        //cur之前的数为左子树  cur到头节点之间的数是右子树 如果右子树有小于root 返回false
        for(int k = cur; k < j; k++){
            if(postorder[k] < root){
                return false;
            }
        }
        return func(postorder, i, cur - 1) && func(postorder, cur, j - 1);
    }
}

    时间复杂度O(N^2)
    空间复杂度O(n)

    0 赞同 0 条回复
  • 阿白 普通 2022年11月5日 下午1:39

    1、根据后序的特点，最后一个位置right是根。自左开始寻找第一个大于根的位置pos，判断其后是否仍有小于根的结点，若有则返回false。
    2、再分别以pos-1为根（左子树）、right-1为根（右子树）进行递归。
    3、时间O（n），空间O（n）

    class Solution {
public:
    bool verifyPostorder(std::vector<int>& postorder) {
        if (postorder.size() == 0)
            return true;
        return verify(postorder, 0, postorder.size() - 1);
    }

        bool verify(std::vector<int> & post, int left, int right)
        {
            if(left >= right)
                return true;
            int root = post[right];
            int p = left;

            while (post[p] <root)
            {
                p++;
            }
            for (int i = p; i < right; ++i)
            {
                if (post[i] < root)
                    return false;
            }

            return verify(post, left, p - 1)&verify(post, p, right - 1);

        }

};
    0 赞同 0 条回复
  • just 普通 2022年11月5日 上午10:30

    //递归分治
    class Solution {
    public:
    bool fun(vector& nums,int start,int end){
    if(start>=end) return true;
    int target=nums[end];
    int pos=start;
    for(int i=start;i<=end;++i){
    if(nums[i]<target) continue;
    else{
    pos=i;
    break;
    }
    }

        for(int i=pos;i<end;++i){
        if(nums[i]<=target) return false;
    }
    return fun(nums,start,pos-1)&&fun(nums,pos,end-1);

}
bool verifyPostorder(vector<int>& postorder) {
    int n=postorder.size();
    return fun(postorder,0,n-1);

}

    };

    0 赞同 0 条回复
  • 你有点可爱喔 普通 2022年11月3日 下午4:36

    时间复杂度O(n)
    空间复杂度O(n)

        class Solution {
        public boolean verifyPostorder(int[] postorder) {
            //后序遍历：左子树、右子树、当前节点
            // 二叉搜索树：左子树节点的值小于当前节点，右子树的节点值的大于当前节点
            if (postorder == null) {
                return false;
            }
            return fun(postorder, 0, postorder.length - 1);
        }

        boolean fun(int[] postorder, int i, int j) {

            if (i >= j) {
                return true;
            }
            //拿到根节点
            int root = postorder[j];
            int p = i;
            //获取第一个大于等于root的元素的位置；这样就能找到右子树的位置
            while (postorder[p] < root) p++;
            //继续遍历p~j-1下标的元素的值是否存在小于的root节点的值
            for (int k = p; k < j; k++) {
                if (postorder[k] < root) {
                    return false;
                }
            }
            return fun(postorder, i, p - 1) && fun(postorder, p, j - 1);

        }
    }
    0 赞同 0 条回复
  • 优秀市民 普通 2022年11月3日 上午10:58

    class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
    def recur(i, j):
    if i >= j:
    return True
    p = i
    while postorder[p] < postorder[j]:
    p+=1
    m = p
    while postorder[p] > postorder[j]:
    p+=1
    return p j and recur(i, m-1) and recur(m, j-1)

        return recur(0, len(postorder)-1)

    递归的去判断，后序遍历中的最后一个节点是根节点，二叉搜索树又有左 > 右的特点，时间复杂度0n^2 空间复杂度on

    0 赞同 0 条回复
  • 马啸天 永久会员 2022年11月3日 上午1:05 
    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if (postorder == null) return true;

        return f(postorder , 0 , postorder.length - 1);
    }

    boolean f(int[] postorder , int i , int j) {
        if (i >= j) return true;

        int root = postorder[j];
        int p = i;
        //寻找第一个比root大的元素下标
        while (postorder[p] < root) p++;
        //找到p后，判断[p,j-1]中，是否有元素比root大，如果大，那就返回false，否则不返回，并且继续遍历
        for (int k = p; k < j; k++) {
            if (postorder[k] < root) return false;
        }

        return f(postorder , i , p - 1) && f(postorder , p , j - 1);
    }
}
    0 赞同 0 条回复
  • yanshuojune 普通 2022年11月3日 上午12:15

    解题思路：根节点为最后一个位置元素，遍历列表找到第一个大于根节点的位置，该位置之前的元素应都小于根节点，之后的元素都大于根节点，否则返回False，同事递归左右两个子树，完成求解。
    时间复杂度：O(n2)
    空间复杂度：O(n)

    class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        def recur(i, j):
            if i >= j:
                return True
            p = i
            while postorder[p] < postorder[j]:
                p += 1
            m = p
            while postorder[p] > postorder[j]:
                p += 1
            return p == j and recur(i, m - 1) and recur(m, j - 1)

        return recur(0, len(postorder) - 1)
    0 赞同 0 条回复
  • mpweixin用户 永久会员 2022年11月2日 下午4:07 
    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return test(postorder,0,postorder.length-1);
    }
    boolean test(int[] postorder,int i,int j){
        if(i>=j) return true;
        int p = i;
        while(postorder[p]<postorder[j]) p++;
        int m = p;
        while(postorder[p]>postorder[j]) p++;
        return p  == j && test(postorder,i,m-1)&&test(postorder,m,j-1); 
    }
}

    1.使用递归的方法
    2.后序遍历最后一个为根节点，我觉得是关键
    3.使用while语句可以得到第一个比根节点大的值

    0 赞同 0 条回复
  • 庄重 普通 2022年11月2日 下午12:22 
    // 思路：
//     1.后序遍历的最后节点为该树的根节点
//     2.比根节点数值小的为左子树节点，比根节点数值大的为右子树节点
//     3.此时问题变为其子问题，判断其左右子树的问题是否为真
class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        if(postorder.empty()) 
            return true;

        return f(postorder, 0, postorder.size()-1);
    }

    //函数功能：判断是否为某二叉搜索树的后序遍历结果
    bool f(vector<int>& postorder, int i, int j){
        //只剩一个节点的时候，或没有节点的时候返回true
        if(i >= j)
            return true;

        int root = postorder[j];
        int k = i;
        //得到所有左子树节点的右一节点位置
        while(postorder[k] < root) 
            ++k;

        for(int idx = k;idx < j; ++idx){
            if(postorder[idx] < root)
                return false;
        }
        //对左右子树进行子问题递归
        return f(postorder ,i ,k-1) && f(postorder ,k ,j-1);
    }
};
//时间复杂度O(n)
//空间复杂度O(n)
    0 赞同 0 条回复
  • y 普通 2022年11月1日 下午11:03 
    var verifyPostorder = function(postorder) {
   if(postorder.length <= 2) return true;
   // 最后一个元素即根节点
   let rootVal = postorder[postorder.length - 1];
   // 找第一个大于根节点的元素
   let index = postorder.findIndex(item => item > rootVal);
   // 分割
   let left = postorder.slice(0, index);
   let right = postorder.slice(index, postorder.length - 1);

   if(Math.min(...right , rootVal) !== rootVal ) return false;
   return verifyPostorder(left) && verifyPostorder(right);
};
    0 赞同 0 条回复
  • 派大星 普通 2022年11月1日 下午7:04 
    //二叉搜索树的规律是根节点小于右子树的所有值大于左子树的所有值，且后序遍历的最后一个值就是根节点，找到序列中第一个比根节点大
//的值用递归的方法分成左子树和右子树进行判断
//时间复杂度O(n^2)
//空间复杂度O(n)
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder==null) return false;
        if (postorder.length==1||postorder.length==0)return true;
        boolean b = verify(postorder);
        return b;

    }
    public boolean verify(int[] postorder){
        if (postorder.length==1||postorder.length==0)return true;
        int a = postorder.length;
        int b = 0;
        for (int i = 0; i < a; i++) {
            if(postorder[i]>=postorder[a-1]){
                b=i;
                break;
            }
        }
        for (int i = b; i < a; i++) {
            if(postorder[i]<postorder[a-1])return false;
        }
        boolean b1 = verify(Arrays.copyOfRange(postorder,0,b));
        if(b1==false)return false;
        boolean b2 = verify(Arrays.copyOfRange(postorder,b,postorder.length-1));
        if(b2==false) return false;
        return true;
    }
}
    0 赞同 0 条回复
  • 西西弗斯的石头 永久会员 2022年11月1日 下午5:11

    当数组顺序排列，时间复杂度O（n ^2）和空间复杂度O(n)都是最坏的

    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        //抓住二叉搜索树的规律，右子树的所有值都比根节点大，左子树的所有值都比根节点小
        if(postorder==null) return true;
        return f(postorder,0,postorder.length-1);

    }
    boolean f(int[] postorder,int l,int r){
        //12345,就会出现l>r的情况
        if(l>=r) return true;
        //先找到根节点
        int root = postorder[r];
        int k = l;
        while(postorder[k]
    0 赞同 0 条回复
  • T 普通 2022年11月1日 下午2:04 
    class Solution {
    /**
    * 递归
    */
    public boolean verifyPostorder(int[] postorder) {
        return recursion(postorder, 0, postorder.length - 1);
    }
    //递归判断，后序遍历结构为左右根，并且根据二叉搜索树特性，寻找中间节点。
    public boolean recursion(int[] postorder, int l, int r) {
        if(l >= r) return true;
        // mid用来记录中间值
        int mid = l;
        int root = postorder[r];
        //从头开始寻找第一个比根节点大的值
        while(postorder[mid] < root) mid++;
        int tmp = mid;
        //postorder[mid]之后的节点都要比该节点大 
        while(tmp < r) {
            if(postorder[tmp++] < root)
                return false;
        }
        return recursion(postorder, l, mid - 1) && recursion(postorder, mid, r - 1);
    }

    /**
     * 辅助栈
     */    

    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> deque = new LinkedList<>();
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--) {
            if(root < postorder[i]) return false;
            // 更新root为栈最接近并且大于当前值的值。root是当前元素的父节点
            while(!deque.isEmpty() && deque.peek() > postorder[i]) {
                root = deque.poll();
            }
            deque.push(postorder[i]);
        }
        return true;
    }
}
    0 赞同 0 条回复
  • 是梦终空 永久会员 2022年11月1日 上午11:18

    递归
    时间O(n^2)
    空间O(n)

    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null)   return true;

        return dfs(postorder,0,postorder.length-1);
    }
    boolean dfs(int[] postorder ,int i ,int j){
        if(i>=j) return true;
        int pre = postorder[j];
        int p = i;
        //第一个大的pre的
        while(postorder[p]<pre) p++;
        //判断第一个大于pre的数的后面几个数有没有比pre小的
        for(int k = p; k < j;k++ ){
            if(postorder[k] < pre)  return false;
        }
        return dfs(postorder,i,p-1) && dfs(postorder,p,j-1);
    }

}
    0 赞同 0 条回复
  • 追 普通 2022年11月1日 上午11:02 
    class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        int n=postorder.size();
        return dfs(postorder,0,n-1);
    }
    //left表示左子序列起始位置下标，root表示根节点所在下标

    bool dfs(vector<int> &postorder, int left, int root) {

        if(left >= root) return true;

        int right=left, i=left;
        //寻找右节点
        while(i<root && postorder[i]<postorder[root]) i++;
        right=i;

        // 检查右子树有没有比根节点小的
        for(i+=1;i<root;i++){
            if(postorder[i]<postorder[root])return false;
        }

        //划分为左右两个子序列
        bool l=dfs(postorder,left,right-1);
        bool r=dfs(postorder,right,root-1);
        return l&&r;
    }
};

    注意函数传入vector容器的形参语法，二叉搜索树的概念

    0 赞同 0 条回复
  • 天然 普通 2022年11月1日 上午12:35

    递归的思路还得多练呀，上道题看的迭代的写法，对二叉搜索树也不得行。找到左子树位置，子树也满足搜索树的要求，右子树也满足，建立递归终止条件，头和尾相交返回True，其他情况进行和头结点比对，还有一点就是对错误情况，右子树存在小于根结点的情况则是False
    时间复杂度O(n^2)，空间复杂度O(n)

    class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        def cur(i,j):
            if i>=j:return True
            p =i
            while postorder[p]<postorder[j]:p+=1
            m = p
            while postorder[p]>postorder[j]:p+=1

            return p==j and cur(i,m-1) and cur(m,p-1)
        return cur(0,len(postorder)-1)
    0 赞同 0 条回复
  • 青木 普通 2022年11月1日 上午12:28 
    /**
    经过上一个题的提示这道题就很容易写出来了，搜索树的后序遍历中最后一个表示根节点，因此用这个节点来检查遍历是否正确，
    我们维护一个cnt保存第一次遍历时所有小于根节点的节点数量(即左子树)，然后再从cnt位置进行遍历，若(右子树)还有比根节点小的数，
    显然不符合搜索树的规则，直接返回false，接下来就是递归检查左子树和右子树，当子树节点数量小于等与1时退出

    时间复杂度O(n^2)
    空间复杂度O(n)
 */
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        int n = postorder.length;
        return function(postorder, 0, n-1);

    }
    public boolean function(int[] postorder, int left, int right) {
        if(postorder==null || postorder.length==0 || left>=right) return true;
        int cnt = 0;
        for(int i=left; i<right; i++){
            if(postorder[i] < postorder[right]) cnt++;
        }
        for(int j=left+cnt; j<right; j++){
            if(postorder[j] < postorder[right]) return false;
        }
        return function(postorder, left, left+cnt-1) && function(postorder, left+cnt, right-1);        
    }
}
    0 赞同 0 条回复
  • 訁訁訁訁訁 普通 2022年10月31日 下午10:34

    时间复杂度O(N^2) 递归中遍历所有节点为N，最差情况下为链表，栈的递归深度为N

    空间复杂度O(N),系统栈O(n)

    递归

    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null) return true;
        return vertify(postorder,0,postorder.length - 1);
    }
    private boolean vertify(int[] postorder,int left,int right){
        if(left >= right) return true;//当区域不合法的时候返回true
        int rootValue = postorder[right];
        int p = left;
        while(p < right && postorder[p] < rootValue){
            p++;
        }
        //找到一个大于root的值，即找到右子树
        for(int i = p;i < right;i++){
            //如果右子树出现小于root的元素，则返回false
            if(postorder[i] < rootValue){
                return false;
            }
        }
        //检查左右子树
        return vertify(postorder,left,p - 1) && vertify(postorder,p,right - 1);
    }
}

    单调栈

    等复习完单调栈之后再写

    0 赞同 0 条回复
  • 波波_1936 普通 2022年10月31日 下午9:54 
        /**
     * 剑指 Offer 33. 二叉搜索树的后序遍历序列
     */
    public boolean verifyPostorder(int[] postorder) {
        //二叉搜索树的性质 左子树节点小于当前节点 右子树的节点大于当前节点
        //后序遍历顺序是： 左 右 当前节点
        //数组中 如果最后一个元素为根的节点的值，则数组前半部分比根小的是左子树，右半部分比根大的值是右子树，如此递归判断，
        //时间复杂度O(n方)
        //空间复杂度O(n)

        if (postorder == null) return true;
        return helper(postorder, 0, postorder.length - 1);

    }

    private boolean helper(int[] postorder, int left, int right) {
        if (left >= right) {
            //一个节点或者没有节点，不需要看了
            return true;
        }
        int mid = left;
        int root = postorder[right];//这是后序遍历的根节点
        while (postorder[mid] < root) {
            //找出第一个比根节点大的值，也就是第一个右节点
            mid++;
        }
        int tmp = mid;//第一个右节点
        while (tmp < right) {
            //所有右节点都要比根节点大才对
            if (postorder[tmp++] < root) {
                return false;
            }
        }
        //递归处理
        return helper(postorder, left, mid - 1) && helper(postorder, mid, right - 1);
    }
    0 赞同 0 条回复
  • So 普通 2022年10月31日 下午9:03 
    class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if (postorder == null) {
            return true;
        }
        return f(postorder, 0, postorder.length - 1);
    }

    boolean f(int[] postorder, int i, int j) {
        if (i >= j) {
            return true;
        }
        int root = postorder[j];
        int p = i;
        while (postorder[p] < root) {
            p++;
        }
        for (int k = p; k < j ; k++) {
            if (postorder[k] < root) {
                return false;
            }
        }
        return f(postorder, i, p - 1) && f(postorder, p, j - 1);
    }
}

    时间：O(n)，空间：O(n)

    0 赞同 0 条回复

# 回答此问题

后才能回答