【二叉树专题】剑指 Offer 33. 二叉搜索树的后序遍历序列-跟着帅地玩副业，开拓第二曲线PlayOffer

岱永久会员 2025年1月7日下午10:12

LCR 152. 验证二叉搜索树的后序遍历序列

class Solution {
    public boolean verifyTreeOrder(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);
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年12月23日下午6:05

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        return verift(postorder, 0, postorder.size()-1);
    }
    bool verift(vector<int>& postorder, int start, int end){
        if(end-start <= 1) return true;
        int idx = start;
        int root = postorder[end];
        bool flag = true;
        for(int i=start; i < end; i++){
            if(flag){
                if(postorder[i] >= root){
                    flag = false;
                    idx = i;
                }
            }
            else{
                if(postorder[i] < root){
                    return false;
                }
            }
        }
        if(flag) return verift(postorder, start, end-1);

        bool left = verift(postorder, start, idx-1);
        if(!left) return false;
        bool right = verift(postorder, idx, end-1);
        if(!right) return false;
        return true;
    }
};

后序的最后一个元素为根节点，以此为分界线，遍历当前数组范围，先找第一个大于根的元素，在其后的数需要判断是否都大于根，如果不满足则返回false，满足则递归左右子树。

0 赞同 0 条回复

youngsir 普通 2024年12月11日上午9:38

二叉搜索树后序遍历得最后一个节点一定是根节点，根据二叉搜索树的性质，左子树的节点值一定小于根节点的值，右子树的节点值一定大于根节点的值，先找到根节点，再从左到右遍历数组，找到第一个大于根节点的值，确定左子树和右子树的范围，再检查左子树和右子树。

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
         return check(postorder,0,postorder.size()-1);
    }
    bool check(vector<int>& postorder,int left,int right){
        if(left>= right) return true;
        int  root = postorder[right];
        int k = left;
        while(k<right && postorder[k]<root){
            k++;
        }
        for(int i = k;i<right;i++){
            if(postorder[i] < root) return false;
        }
        if(!check(postorder,left,k-1)) return false;
        if(!check(postorder,k,right-1)) return false;
        return true;
    }
};

0 赞同 0 条回复

陆狗陆狗普通 2024年12月5日下午11:28

解题思路
1、后续遍历：最后一个输出的点是根节点
2、二叉搜索树：输出顺序一定是，（x<根节点）（根节点<y）（根节点）。根节点是左子树x的最大值，根节点是右子树y的最小值。左子树、右子树也满足二叉搜索树的性质。
可以取出根节点，从左到右遍历整个数组，找到一个大于根节点的元素A，那么（0，A-1）就是左子树，（A，尾节点-1）就是右子树。左子树和右子树也满足二叉搜索树的性质。

class Solution {

    public boolean verifyTreeOrder(int[] postorder) {
        if(postorder==null || postorder.length==0){
            return true;
        }
        return verifySuccess(postorder,0,postorder.length-1);
    }

    public boolean verifySuccess(int[] postorder,int beginIndex,int endIndex){
        // 说明只有1个节点了，肯定是true，递归的出口
        if(endIndex<=beginIndex){
            return true;
        }
        // 因为后续排列，尾节点就是root节点
        // 因为二叉搜索树，比root值小的就是左子树的范围，比root值大的就是右子树的范围
        // 但是不能只比较一次，因为左子树（一堆数据）的子树也要满足二叉搜索树的性质
        int rootValue=postorder[endIndex];
        int current=beginIndex;
        while(postorder[current]<rootValue){
            current++;
        }
        // index>=current的值都应该大于rootValue
        int next=current;
        while(next<=endIndex){
            if(postorder[next]<rootValue){
                return false;
            }
            next++;
        }
        // 校验子树
        return verifySuccess(postorder,beginIndex,current-1) && verifySuccess(postorder,current,endIndex-1);
    }
}

0 赞同 0 条回复

Pendulumpal 普通 2024年12月2日下午9:46

按照二叉搜索树的定义，递归分治

class Solution {
    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);
    }
    public boolean verifyTreeOrder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
}

0 赞同 0 条回复

Jerry 普通 2024年12月2日下午9:15

class Solution {
public:
    bool verifyTreeOrder(vector& postorder) {
        return verifyTreeOrderHelper(postorder, 0, postorder.size()-1);
    }
    bool verifyTreeOrderHelper(vector& postorder, int start, int end){
        if(start > end) return true;
        if(start == end) return true;
        int rootval = postorder[end];
        int lessindex = INT_MIN;
        int greaterindex = INT_MAX;
        for(int i = start; i <= end-1; i++){
            if(postorder[i] > rootval){
                greaterindex = i;
                break;
            }
        }
        for(int i = end-1; i >= start; i--){
            if(postorder[i] < rootval){
                lessindex = i;
                break;
            }
        }
        if(lessindex > greaterindex) return false;
        if(greaterindex == INT_MAX || lessindex == INT_MIN){
            return verifyTreeOrderHelper(postorder, start, end-1);
        }
        return verifyTreeOrderHelper(postorder, start, lessindex)&&verifyTreeOrderHelper(postorder, greaterindex, end-1);
    }
};

时间o(n^2)
空间o(n)
错误点注意：刚开始写if(start > end) return false;，会有空树用例失败，空树默认return true：if(start > end) return true;

0 赞同 0 条回复

lQl 永久会员 2024年12月2日下午7:51

跟第一题类似,递归

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        int n = postorder.length;
        return helper(postorder, 0, n - 1);

    }

    public boolean helper(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int p = left;
        while (postorder[p] < postorder[right])
            p++;
        int m = p;
        while (postorder[p] > postorder[right])
            p++;

        return p == right && helper(postorder, left, m - 1) && helper(postorder, m, right - 1);
    }
}

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

0 赞同 0 条回复

晓宇普通 2024年12月2日下午5:45

class Solution {
public:
    bool verifyTreeOrder(vector& postorder) {
        if(postorder.empty()) return true;
        return f(postorder, 0, postorder.size() - 1);
    }

    bool f(vector& postorder, int l, int r){
        if(l >= r) return true;
        int root_val = postorder[r];
        int p = l;  // 左右子树分界限点，数组中根节点首个右子树索引
        while(postorder[p] < root_val) p++;
        for(int i = p + 1;i < r;i ++){
            if(postorder[i] < root_val) return false;
        }

        return f(postorder, l, p - 1) && f(postorder, p, r - 1);
    }
};
// 思路：递归。二叉搜索树的特点
（1）确定根节点：后序遍历为序列的末尾节点；
（2）确定根节点左右子树的分界；从左往右数组中首个大于根节点值的节点，即为右子树的首节点；
（3）确定子问题（依次判别左右子树），及边界条件（直到叶子节点）。
（4）递归求解
// 时间复杂度：o(nlogn);空间复杂度：o(n)

0 赞同 0 条回复

Aatorx 永久会员 2024年12月2日下午4:45

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        if (postorder.empty()){
            return true;
        }
        return recur(postorder, 0, postorder.size()-1);
    }
    bool recur(vector<int>& postorder, int l, int r){
        if (l>r){
            return true;
        }
        int p = l;
        while(postorder[p] < postorder[r]){
            p++;
        }
        int m = p;
        for(int i = p; i < r; i++){
            if (postorder[i] < postorder[r]){
                return false;
            }
        }
        return recur(postorder, l, m-1) && recur(postorder, m, r-1);
    }
};

后续遍历根节点为最后一个节点，利用二叉搜索树特点，可以遍历数组比根节点小的点为左子树节点，比根节点大的为右子树节点，然后递归判断左右子树是否满足。
时间复杂度O(N^2)，空间复杂度O(N)。

0 赞同 0 条回复

黑键〰普通 2024年12月2日下午2:58

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyTreeOrder = function(postorder) {
    if(!postorder.length) return true
    const f = (postorder, i, j) => {
        // 先判断终止条件
        if(i > j) return true
        let curroot = postorder[j]
        let idx = i
        // 查找第一个比根节点大的元素
        while(postorder[idx] < curroot) idx++
        // 在右子树中查找是否有比根节点小的元素
        for(let i=idx; i<j; i++) {
            if(postorder[i] < curroot) {
                return false
            }
        }
        return f(postorder, i, idx-1) && f(postorder, idx, j-1)
    }
    return f(postorder, 0, postorder.length-1)
};

思路：看完视频之后写的，还是根据后序遍历的规则，以及二叉搜索树的规律来综合思考
找到根节点之后通过找到第一个不小于根节点的数，切分左右子树
然后从右子树中搜索是否有不符合二叉搜索树规则的值，左右逐层递归

0 赞同 0 条回复

遇事不决睡大觉普通 2024年12月1日下午11:55

class Solution {
public boolean verifyTreeOrder(int[] postorder) {
// 创建一个栈用于存储节点值
Stack 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]);
    }
    // 如果遍历完没有发现不符合的情况，则返回true
    return true;
}

}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月1日上午10:47

思路：使用分治的思想进行递归实现，在树及其子树中找出数组对应第一个大于“根”的值，然后判断之后的值是否有小于该“根”值的结点，如果有则false。当左右边界重合时说明前面所有的树都满足条件，即可终止并返回ture。
class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        if(postorder.length<=0) return true;
        return verify(postorder,0,postorder.length-1);
    }
    public boolean verify(int[] postorder,int left,int right){
        if(left>=right) return true;
        int root=postorder[right];
        int tmp=left;
        while(postorder[tmp]<root) tmp++;
        for(int i=tmp;i<right;i++){
            if(postorder[i]<root) return false;
        }
        return verify(postorder,left,tmp-1)&&verify(postorder,tmp,right-1);
    }
}
时间复杂度：O（n²）
空间复杂度：O（n）

0 赞同 0 条回复

Kisara 普通 2024年11月30日下午10:02

分割左右子树，后序遍历先找到根节点的值，然后遍历数组找到第一个大于根节点的数值作为分割点，这是左右子树的分割点，然后从分割点向后遍历，只要postorder[index]大于根节点的值就向后继续，最后相等之后跳出循环，若是最后判断index不等于end，说明右子树并不是全部大于根节点，不合法，再递归判断此节点的左右子树，最后三个条件一起，得出结果

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        return isBalanceTree(postorder,0,postorder.length-1);
    }

    boolean isBalanceTree(int[] postorder,int start,int end){
        if(start>end) return true;
        int val=postorder[postorder.length-1];
        int index=start;
        int midindex=0;
        while(postorder[index]<postorder[end]) index++;
        midindex=index;
        while(postorder[index]>postorder[end]){
            index++;
        }

        boolean left=isBalanceTree(postorder,start,midindex-1);
        boolean right=isBalanceTree(postorder,midindex,end-1);

        return index==end&&left&&right;
    }
}

on on

0 赞同 0 条回复

苯庸普通 2024年11月30日下午7:27

class Solution {
public boolean verifyTreeOrder(int[] postorder) {
// [ [小于n][大于n] n]
boolean flag = false;
for(int i = 0; i < postorder.length; i++){
for(int j = i-1; j >= 0; j–){
if(postorder[j] < postorder[i]){
flag = true;
}
if(flag && postorder[j] > postorder[i]){
return false;
}
}
flag = false;
}
return true;
}
}
思路：从当前节点往前遍历，遍历到比当前点小后记录flag，然后继续遍历，如果出现比当前点小的值则返回false；
时间：O（n2）
空间：O（1）

0 赞同 0 条回复

Renasc 普通 2024年11月30日下午4:17

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

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

    public boolean f(int[] postorder, int start, int end) {
        // 退出条件
        if (start >= end) return true;

        // 后序遍历最后一个元素是根节点
        int root = postorder[end];

        // 找到比根节点大于等于第一个元素
        int curr = start;
        while (postorder[curr] < root) curr++;

        // 检查从curr到end-1有没有比root小的元素，有的话说明这不是二叉搜索树
        for (int i=curr; i<end; i++) {
            if (postorder[i] < root) {
                return false;
            }
        }

        // 返回递归左右子树的结果
        return f(postorder, 0, curr-1) && f(postorder, curr, end-1);
    }
}

0 赞同 0 条回复

月下足迹普通 2024年11月30日下午3:00

class Solution {
public boolean verifyTreeOrder(int[] postorder) {
if (postorder null || postorder.length 0) return true;
return verify(postorder,0,postorder.length-1);
}

public boolean verify(int[] postorder ,int start, int end) {

    if (start >= end) return true; 
    int rootValue = postorder[end];

    //找第一个大于根结点的索引
    int splitIndex = start;
    while (splitIndex < end && postorder[splitIndex] < rootValue) splitIndex++;

    //验证右子树的值是否都大于根结点
    for (int i = splitIndex; i < end; i++) {
        if (postorder[i] < rootValue) return false; 
    }

    return verify(postorder, start, splitIndex - 1) && verify(postorder, splitIndex, end -1);
}

}

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日上午1:00

/**
思路：
二叉搜索树后序遍历结果中，最后一个元素为根节点，根据性质，二叉搜索树左子树值全部小于根节点，
右子树值全部大于根节点，则首先我们需要确保能从将后序遍历数组切成两半，前一半全部小于root，后一半全部大于root
在递归判断前一半和后一半是否满足性质

复杂度分析：
后序遍历数组从后往前遍历取root，每次还需额外判断数组前一半和后一半是否满足约束，复杂度O(n**2)
 */

class Solution {
    int[] postorder = null;
    public boolean verifyTreeOrder(int[] postorder) {
        if (postorder.length <= 1){
            return true;
        }

        this.postorder = postorder;
        return check(0, postorder.length-1);

    }

    public boolean check(int start, int end){
        if (start >= end){
            return true;
        }

        int root = postorder[end];
        int leftSize = 0;
        for (int i = start; i < end; i++){
            if (postorder[i] < root){
                leftSize++;
            } else{
                break;
            }
        }

        boolean rightValid = true;
        for (int i = start + leftSize; i < end; i++){
            if (postorder[i] < root){
                rightValid = false;
            }
        }

        return rightValid && check(start, start+leftSize-1) && check(start+leftSize, end-1);


    }
}

0 赞同 0 条回复

jaron 普通 2024年11月29日下午11:06

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        if (postorder == null) {
            return true;
        }
        return f(postorder, 0, postorder.length - 1);
    }

    public boolean f(int[] post, int l, int r) {
        if (l >= r) {
            return true;
        }
        // 最后一个元素是根节点
        int head = post[r];
        int i = 0;
        // 根据左小右大，区分左子树
        while (post[i] < head) {
            i++;
        }
        // 看看右子树是不是都大于根节点
        for (int k = i; k <= r; k++) {
            if (post[k] < head) {
                return false;
            }
        }
        // 递归左右子树
        return f(post, l, i - 1) && f(post, i, r - 1);
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年11月29日下午10:27

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        // 左子树的值都小于根节点的值
        // 右子树的值都大于根节点值
        return check(postorder, 0, postorder.length - 1);
    }

    // 判断 postorder[i, j] 之内的元素是否满足二叉搜索树的条件 
    private boolean check(int[] postorder, int i, int j) {
        if (i >= j) {
            return true;
        }

        // 一棵二叉搜索树根节点的值一定是后序遍历的最后一个元素
        int root = postorder[j];

        // 寻找左子树与右子树的分割点
        int left = i;
        while (left < j && postorder[left] <= root) {
            left++;
        }
        // 此时，left 就是 postorder 右子树的起始索引
        int right = left;
        while (right < j && postorder[right] >= root) {
            right++;
        }
        // 此时 right 应该 == j
        if (right != j) {
            return false;
        }

        // 遍历 root 的左右子树是否也满足二叉搜索树的后序遍历结果
        return check(postorder, i, left - 1) && check(postorder, left, j - 1);
    }
}

思路：根据二叉搜索树的性质判断左右子树在 postorder 上的区间，并依次递归的判断左右子树是否也满足二叉搜索树的后序遍历序列。
时间复杂度：最坏情况是 O(n^2^)，平均情况 O(nlogn)。
空间复杂度：O(n)，递归调用栈空间。

0 赞同 0 条回复

秋山丽奈普通 2024年11月29日下午8:25

思路：首先根据搜索树性质划分出左右子树依次递归判断左右子树

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        /**
        二叉搜索树性质
            非空左子树的所有键值小于其根结点的键值
            非空右子树的所有键值大于其根结点的键值
            左、右子树都是二叉搜索树

            [左子树][右子树] root
            x ∈ 左子树 : x.val < root.val
            x ∈ 右子树 : x.val > root.val
         */

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

    }

    boolean recur(int[] postorder, int head, int tail) {
        if(head >= tail) return true;
        int index = head;
        // 第一个大于 root.val 的即为 root 的右节点 
        while(postorder[index] < postorder[tail]){
            index ++;
        } 

        int right = index;
        while(postorder[index] > postorder[tail]){
            index ++;
        } 
        return index == tail && recur(postorder, head, right - 1) && recur(postorder, right, tail - 1);
    }

}

0 赞同 0 条回复

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

共以下 20 个回答

LCR 152. 验证二叉搜索树的后序遍历序列

# 回答此问题取消回复

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

共以下 20 个回答

LCR 152. 验证二叉搜索树的后序遍历序列

# 回答此问题 取消回复

# 回答此问题取消回复