剑指offer 二叉搜索树的后序遍历序列

╰半橙微兮° 2024-04-17 05:39 73阅读 0赞

# [剑指offer题型分类及各题的代码及解题思路][offer] #

## 1、题目描述 ##

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

## 2、初始结构定义如下： ##

class Solution {
    public:
        bool VerifySquenceOfBST(vector<int> sequence) {}
    };

## 3、思路 ##

① 若二叉搜索树为空，则返回false；

② 因为是后序遍历，所以数组最后一个元素为根节点；

③ 在数组中找到右子树部分，用 mid 标记这部分第一个元素的位置；

④ 那么左子数在数组中的范围为（0，mid - 1）；

⑤ 递归判断左子树部分是否为二叉搜索树，若有不满足的子树，则返回false，否则遍历整个左子树；

⑥ 递归判断右子树部分是否为二叉搜索树，若有不满足的子树，则返回false，否则遍历整个右子树；

## 4、C++实现代码如下： ##

class Solution {
    public:
        bool VerifySquenceOfBST (vector<int> sequence) {
            //数组为空
            if(!sequence.size())
                return false;
            
            //判断是否为二叉搜索树
            return Judge(sequence, 0, sequence.size()-1);
        }
        
        bool Judge (vector<int> res, int left, int right)
        {
            //left > right，说明只有一个叶结点
            //left == right，说明为空树，即无子节点
            if(left >= right)
                return true;
            
            //先让mid指向根结点
            int mid = right;
            
            //找到右子树部分的最左边的值（左右子树分界点）
            while(res[mid - 1] > res[right])
                mid--;
            
            //若左子树存在大于根节点的值，则该二叉树非二叉搜索树
            for (int j = mid-1; j >= left; --j)
            {
                if (res[j] > res[right])
                    return false;
            }
            
            //递归判断左右子树
            return Judge(res, left, mid-1) && Judge(res, mid, right-1);
        }
    };

[offer]: https://blog.csdn.net/qq_26079093/article/details/96605538