题解 | 二叉搜索树的后序遍历序列

#include <vector>
class Solution {
public:

    bool dfsVerify(vector<int>& seq, int l, int r){
        if(l==r||l>r) return true;
        //else if(l>r) return false;
        bool flag1 = true, flag2 = true, flag3 = true;
        int ll = l-1;
        for(int i = r-1; i >= l; --i){
            if(seq[i]<seq[r]){
                ll = i;
                break;
            }
        }
        for(int i = ll; ll >= l&&i >= l; --i){
            if(seq[i]>seq[r]){
                flag1 = false;
                break;
            }
        }
        flag2 = dfsVerify(seq, l, ll);
        flag3 = dfsVerify(seq, ll+1, r-1);
        return flag1&&flag2&&flag3;
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        return dfsVerify(sequence, 0, sequence.size()-1);
    }
};

方法一（递归）：

树的题目很容易就想到递归处理，左小右大是二叉搜索树。如果所有子树都符合这个规律那么它就是二叉搜索树。

所以我们找到每一棵树都遍历一遍就可以了。

时间复杂度是O(n^2)；空间复杂度是O(n)，当退化成链表的时候是n。

#include <climits>
#include <stack>
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        stack<int> s;
        int root = INT_MAX;
        for(int i = sequence.size()-1; i >= 0; --i){
            if(root<sequence[i]) return false;
            while(!s.empty()&&s.top()>sequence[i]){
                root = s.top();
                s.pop();
            }
            s.push(sequence[i]);
        }
        return true;
    }
};

方法二（子问题处理，假说检验）：

这个其实也是子问题处理，但是我们换一种观察子树是否合格的方式，这需要对后序遍历有理解。

其实就是倒着看中右左是另一种先序遍历（左右顺序互换），那么就相当于先往右走走到最深，然后看看左边有没有，没有再返回。

这样的话我们就可以一直往右到反而变小的位置，这个位置有两种可能，一种是到左子树去了，另一种可能就是返回到上级的左子树去了。

因为相当于是先序遍历，所以该子树的根节点肯定是被访问过的，要找到这个根节点就要到下一个节点比左节点还小的位置（上方不会作为整体左子树的，因为有整体左子树肯定有更近的左子树节点，在处理那个左子树节点的时候这个更高点的根节点已经处理过了。（也就是这次虽然没有到更小的位置但是栈已经空了）

这样我们就可以找全每一个有左子树的根节点，因为是通过走完所有右子树得到的，所以往后只有该根节点的左子树部分（直到再次被换root），因此只考虑比当前根节点小就可以（因为我们是默认右子树是对的的情况往下走的，所以只用检查这样的话左子树是否对应成功，这相当于一种假设正确那么它应该是这样，如果不是这样就错误的假说检验法）。

所以我们唯一的判错机制是这个左边（当前正在经历的sequence[i]）比root大，如果整个过程中没有判错就是判对。