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

YOLO 普通 2024年3月30日下午11:18

/*输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 */
class Solution {
    public boolean verifyTreeOrder(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++;   //获取第一个>=root等元素的位置
        }
        for(int k = p ; k < j ; k++){   //判断p~j-1范围是否存在>root的元素
            if(postorder[k] < root){
                return false;
            }
        }
        return f(postorder , i ,p-1)&&f(postorder , p , j-1);
    }
}

0 赞同 0 条回复

kfaebot 普通 2024年3月21日下午9:56

class Solution {
public:
    //步骤1：确定返回值和参数
    bool check(vector<int>& postorder,int begin,int end){
        //步骤2：确定终止条件
        if(begin>=end-1){
            return true;
        }

        //考虑后序遍历序列的最后一个元素是中间节点
        //找到后序遍历序列中第一个大于中间节点的元素作为左右子树分割点
        int root=postorder[end-1];
        int tmp;
        for(int i=begin;i<end-1;i++){
            if(postorder[i]>root){
                tmp=i;
                break;
            }
        }
        for(int i=tmp;i<end-1;i++){
            if(postorder[i]<root){
                return false;
            }
        }

        //左子树的区间，左闭右开
        int left_begin=begin;
        int left_end=tmp;
        //右子树的区间，左闭右开
        int right_begin=tmp;
        int right_end=end-1;

        bool l=check(postorder,left_begin,left_end);
        bool r=check(postorder,right_begin,right_end);

        return l&&r;
    }

    bool verifyTreeOrder(vector<int>& postorder) {
        return check(postorder,0,postorder.size());
    }
};

0 赞同 0 条回复

NULL 普通 2024年3月20日下午9:55

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

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

public boolean judge(int[] postorder, int l, int r){
    if(l >= r)return true;// 递归出口
    int root = postorder[r]; // 后序的最后的节点，应该是根节点
    int index = l; // 从左往右找比根大的，找到的就是右子树
    while(postorder[index] < root){
        index++;
    }
    for(int i = index; i < r; i++){// 右子树全部比根大
        if(postorder[i] <= root)return false;
    }
    return judge(postorder, l, index - 1) && judge(postorder, index, r - 1);

}

}

0 赞同 0 条回复

紫芝普通 2024年3月15日下午10:38

思路：思路与地哥在视频中讲解的一致，使用递归的方式判断后序遍历序列是否正确

“`c++
class Solution {
public:
bool verifyTreeOrder(vector& postorder) {
if (postorder.size() <= 1) return true; return f(postorder, 0, postorder.size()-1); } bool f(vector& postorder, int left, int right) {
if (left >= right) return true;
int idx = left;
while (idx < right && postorder[idx] <= postorder[right]) idx++; for (int i=idx; i

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月13日下午6:48

class Solution {
    // 采用栈的先进后出特性保证栈顶元素肯定是最大元素
    // 二叉搜索树的特性是左子小于根节点小于右子
    // 当从后向前遍历时，如果是搜索二叉树总能保证 rootVal 存放的值大于即将遍历的值
    public boolean verifyTreeOrder(int[] postorder) {
        Stack<Integer> stack = new Stack<>();
        int size = postorder.length;
        int rootVal = Integer.MAX_VALUE;
        for (int i = size - 1; i >= 0; i--) {
            if (postorder[i] > rootVal) {
                return false;
            }
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                rootVal = stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
    // 时间复杂度为 O(n)
    // 空间复杂度为 O(n)
}

0 赞同 0 条回复

一个达不刘普通 2024年3月13日下午3:16

class Solution {
public:
bool verifyTreeOrder(vector& postorder) {

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

}

private:
bool f(vector &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 pj&&f(postorder,i,m-1)&& f(postorder,m,j-1);//递归左右子树。
}
};

0 赞同 0 条回复

mpweixin用户普通 2024年3月12日下午10:19

java
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 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月12日下午9:14

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 i,int j){
        if(i>=j) return true; // 为什么？只有一个结点或没有结点，判断为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);
    }
}

0 赞同 0 条回复

RunAsOne 普通 2024年3月12日下午4:18

第一次打卡二叉搜索树

class Solution(object):
    def verifyTreeOrder(self, postorder):
        """
        :type postorder: List[int]
        :rtype: bool
        """
        if not postorder:
            return True

        def cur(postorder, l, r):
            if l >= r:
                return True
            root = postorder[r]
            p = l
            for i in range(len(postorder)):
                if postorder[p] < root:
                    p = i
            for j in range(p,r):
                if postorder[j] < root:
                    return False
            return cur(postorder, l, p - 1) and cur(postorder, p, r - 1)

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

0 赞同 0 条回复

神经蛙普通 2024年3月12日上午12:25

class Solution {
public:
bool verifyTreeOrder(vector& postorder) {
if (postorder.empty()) {
return true;
}

    function<bool(int, int)> f = [&](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(i, p - 1) && f(p, j - 1);
    };

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

};
打卡：先找到比根节点大的第一个数，然后把数组拆分成左右子树，分别递归

0 赞同 0 条回复

MARS 普通 2024年3月11日下午11:49

day9第二题

function verifyTreeOrder(postorder: number[]): boolean {
    if (postorder.length == 0) return true
    return tr(postorder, 0, postorder.length - 1)

    function tr(postorder: number[], i: number, j: number): boolean {
        if (i >= j) return true
        let root = postorder[j]
        let p = i
        while (postorder[p] < root) p++

        for(let k = p;k<j;k++){
            if(postorder[k]<root) return false
        }
        return tr(postorder,i,p-1) && tr(postorder,p,j-1) 
    }
};

0 赞同 0 条回复

言之命至普通 2024年3月11日下午9:57

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 ~ j -1 这个范围是否存在小于root的元素
        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)

0 赞同 0 条回复

Free 普通 2024年3月11日下午8:46

class Solution 
{
public:
    bool verifyTreeOrder(vector<int>& postorder) 
    {
        return verifyTreeOrder(postorder, 0, postorder.size() - 1);
    }

    bool verifyTreeOrder(vector<int>& postorder, int left, int rooti)
    {
        if(left >= rooti)
            return true;
        int i = left;
        while(postorder[i] < postorder[rooti])
            i++;
        int mid = i;
        while(postorder[i] > postorder[rooti])
            i++;
        return i == rooti && verifyTreeOrder(postorder, left, mid - 1) && verifyTreeOrder(postorder, mid, rooti - 1);
    }
};

时空复杂度O(N)

0 赞同 0 条回复

Jimmy 普通 2024年3月11日下午8:33

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        if(postorder.size() == 0){
            return true;
        }

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

    bool f(vector<int> postorder,int l,int r){
        if(l>r){
            return true;
        }
        //由于是后序遍历，最后一个元素一定是根节点
        //找第一个比根节点大的元素的位置
        int p=0;
        while(postorder[p]<postorder[r])p++;
        for(int i=p;i<r;i++){
            if(postorder[i]<postorder[r]){
                return false;
            }
        }
        return f(postorder,l,p-1) && f(postorder,p,r-1);
    }
    // 时间复杂度：最差O(n^2)
    // 空间复杂度：最差(n)（退化成链表）
};

0 赞同 0 条回复

方铎码农普通 2024年3月11日下午4:23

// 二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：
// 非空左子树的所有键值小于其根结点的键值。
// 非空右子树的所有键值大于其根结点的键值。
// 左、右子树都是二叉搜索树。

//后序搜索中，最后的节点是根节点，

class Solution {

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

    private boolean recur(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 && recur(postorder, left, m-1) && recur(postorder, m, right-1);
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月11日下午3:40

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 pj && recur(postorder,i,m-1) && recur(postorder,m,j-1);
}
思路：
根节点是后序遍历中的最后一个点，递归确定每个树节点的左子树是不是都小于根节点，再看右子树是不是都大于

0 赞同 0 条回复

Yuki 永久会员 2024年3月11日下午1:35

打卡
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solutions/2680161/yan-zheng-er-cha-sou-suo-shu-by-yukislab-4twz

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月11日上午9:23

打卡

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        return isPostorder(postorder, 0, postorder.size() - 1);
    }
private:
    bool isPostorder(vector<int>& post, int i, int j) {
        if(i >= j) return true;
        int rootval = post[j];
        int p = i;
        while(post[p] < post[j]) ++p; // 找到第一个＞根的数post[p],则post[p]左边的数都<root，右边的数都>root
        for(int k = p; k <= j; ++k) { // 若post[p]右边出现<root的数，则不是二叉搜索树
            if(post[k] < rootval) return false;
        }
        // 递归继续判断root的左右子树是否满足
        return isPostorder(post, i, p - 1) && isPostorder(post, p, j - 1);
    }

0 赞同 0 条回复

云无深雁影普通 2024年3月11日上午1:16

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

}
private boolean rec(int[] postorder,int begin,int end){
    if(begin >= end)
        return true;
    int root = postorder[end];
    int left = begin;
    while(left <= end && postorder[left] < root){
        left++;
    }
    for(int i = left; i < end; i++){
        if(postorder[i] < root)
            return false;
    }
    left--;
    return rec(postorder,begin,left)&&rec(postorder,left+1,end-1);
}

}//递归写法
//时间复杂度On2
//空间复杂度On

0 赞同 0 条回复

机电皮怪永久会员 2024年3月10日下午11:59

“`C++
class Solution {
public:
bool verifyTreeOrder(vector& postorder) {
return test(postorder, 0, postorder.size() – 1);
}
private:
bool test(vector& postorder, int left, int right)
{
//递归结束条件
if(left >= right)
{
return true;
}
int cur = left;
int last = postorder[right];
while(postorder[cur] < last) { cur++; } //根节点 int root = cur; for(int i = cur; i < right; i++) { if(postorder[i] < last) { return false; } } return test(postorder, left, root - 1 ) && test(postorder, root, right - 1); } }; ```

0 赞同 0 条回复

heathhou 普通 2024年3月10日下午10:36

class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        if(postorder.empty()){
            return true;
        }

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

    // 递归函数：判断后序遍历postorder保存的是不是一颗二叉搜索树
    bool f(vector<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);
    }


};

0 赞同 0 条回复

王位詮釋普通 2024年3月10日下午10:10

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        return recur(postorder,0,postorder.length-1);
    }
    public boolean recur(int[] postorder,int i,int j){
        if(i>=j){
            return true;
        }
        //j索引代表的是根节点
        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 条回复

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

共以下 22 个回答

# 回答此问题取消回复

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

共以下 22 个回答

# 回答此问题 取消回复

# 回答此问题取消回复