题目描述

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

提示：
1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。
2.该题我们约定空树不是二叉搜索树
3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历.

题解:

图示引自:NumPy

代码:

class Solution {
public:
    bool check(vector<int> sequence,int left,int right){
        if(left >= right) return true;//递归出口
        //找到根节点
        int root = sequence[right];
        
        //找到右子树左节点的位置right
        //注意：当找到之后，就意味着搜索二叉树的右子树肯定存在且右子树是搜索二叉树
        //因为搜索二叉树根节点的右子树节点的值都比根节点大，
        //如果根节点左边的节点小于根节点，那么说明该数组是不是某二叉搜索树的后序遍历的结果
        int j = right-1;;//
        while(j >= 0 && sequence[j] > root)
            j--; // 完成最后一个循环时，right指向左子树的最右边节点
        
        //检查左子树是不是存在大于根节点的树，如果存在，说明该数组是不是某二叉搜索树的后序遍历的结果
        //如果不存在，说明是
        for(int i = left;i<=j;i++){
            if(sequence[i] > root)
                return false;//左子树存在比根节点的值大的节点，返回false
        }
        return check(sequence,left,j) && check(sequence, j+1,right-1);
    }

    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        int n = sequence.size()-1;
        return check(sequence,0,n);
        
    }
};