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

小灰灰 2022-01-22 13:57 109阅读 0赞

## 题目描述 ##

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

【分析】理解后序遍历是解决本题的关键。后序遍历的最后一个节点是根节点，根据二叉搜索树的定义，我们只要找到左子树和右子树，如果左子树的节点小于根节点，右子树的节点全部大于根节点。并且在之后的递归子树中，依然满足这个规律（二叉搜索树的子树也是二叉搜索树），则可以确定这个序列是二叉搜索树的后序遍历。

class Solution {
    public:
        bool VerifySquenceOfBST(vector<int> sequence) {
            return isLastorder(sequence,0,sequence.size()-1);
        }
        bool isLastorder(vector<int>& s,int begin,int end){
            if(s.empty()||begin > end)
                return false;
            int root = s[end];
            int i = begin;
            for(;i<end;++i){//找到右子树的第一个节点
                if(s[i]>root)
                    break;
            }
            for(int j = i;j < end;++j){//判断右子树是否符合后序遍历的定义
                if(s[j] < root)
                    return false;
            }
            //至此判断完当前节点的左右子树都符合后序遍历
            //然后递归的去判断左右子树
            bool left = true;
            if(i > begin){
                left = isLastorder(s,begin,i-1);
            }
            bool right = true;
            if(i < end - 1)
                right = isLastorder(s,i,end - 1);
            return left && right;
        }
    };