C++——判断二叉搜索树的后续遍历结果

最新推荐文章于 2025-04-11 15:47:45 发布

L一抹阳光

最新推荐文章于 2025-04-11 15:47:45 发布

阅读量225

点赞数

分类专栏： C++ 文章标签：二叉搜索树后序遍历 C++

本文链接：https://blog.csdn.net/ldm_666/article/details/117032671

版权

C++ 专栏收录该内容

47 篇文章

订阅专栏

二叉搜索树：任意一个节点的值都满足大于左孩子节点值，且小于右孩子节点值。二叉搜索树的中序遍历结果是有序的。

判断一个数组是否满足二叉搜索树的后续遍历结果，递归调用judge函数，该函数接收三个参数，包括带判断的序列，索引的范围。后续遍历的最后一个值是根节点的值，我们从后面开始遍历，直到找到不大于根节点的值的索引 i，这个过程是右子树的遍历；然后再遍历从索引起始点到 i 范围的值，若存在大于根节点的值，返回false；递归判断左子树和右子树是否都满足要求。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
         int len=sequence.size();
        if(len==0) return false;
        if(len==1) return true;
        return judge(sequence,0,len-1);
    }
    bool judge(vector<int>seq,int start,int root)
    {
        if(start>=root) return true;
        int i=root-1;
        while(i>start&&seq[i]>seq[root])
            i--;
        for(int j=start;j<i;j++)
        {
            if(seq[j]>seq[root])
                return false;
        }
        return judge(seq,start,i)&&judge(seq,i+1,root-1);
    }
};