二叉搜索树

定义

二叉搜索树是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：

若其左子树存在，则其左子树中每个节点的值都不大于该节点值；
若其右子树存在，则其右子树中每个节点的值都不小于该节点值。

示例：

图片说明

题解：

可以利用 二叉搜索树的根节点是左右节点限制这个条件 ， 从最底部开始判断。

由于一个正确的遍历序列，我们可以在它任意一个位置故意篡改，因此势必要遍历所有的元素才能确定它的正确性，所以个人认为，这个问题的时间复杂度下界应该就是O(n)。

具体来说，二叉搜索树的关键特征是：对于任意一棵子树，均有“左子树<根节点<右子树”，因此，它的根节点约束了它左右子树的取值范围，二叉搜索树的根root是它左子树值的上限（max），同时是它右子树值的下限（min）。如果我们从根节点出发往下走，那么高层祖辈节点序列就会不停地对低层未遍历节点形成一个上下限约束，只要低层节点没有违背这个约束，那么它就是合法的，否则，序列就是不合法的。

因为后序遍历的一些特性，我们可以从右到左倒序访问给定的序列，因为后序遍历的最后一个元素是根节点，倒序访问就相当于是从根到叶，从右到左的访问顺序，从根到叶可以让我们利用祖辈节点提供的上下限约束信息来判断孩子节点合法性，具体步骤如下：

如果当前元素 > 上一个元素，这说明当前元素可能是上一个元素的右孩子，这时候：
如果当前元素突破max上限约束，说明祖辈中存在 “左子树 > 根” 的情况，违背了搜索树的定义（尝试把图中4的值换成7，那么就有子辈7 > 祖辈max约束5，搜索树不成立）；
否则，当前元素就是上一个元素的右孩子，当前元素将成为新的祖辈节点，为后续节点提供约束；

如果当前元素 < 上一个元素，这就说明当前元素是某个祖辈节点的左孩子，这时候：
我们需要找出这个祖辈节点，并将该祖辈的右子树节点全部丢弃（因为它的右子树结构已经确定，无法为后续节点提供帮助），该祖辈节点的值将成为新的max上限约束，当前元素将成为新的祖辈节点，继续为后续节点提供约束；

图片说明

因此，我们需要使用一个栈来存储已经确定了的祖辈节点，当新节点的合法性被确定时，入栈，当算法需要寻找当前节点是谁的左孩子时，出栈；

图片说明 

import java.util.Stack;

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length<1) return false;

        Stack<Integer> roots = new Stack<>();
        roots.push(Integer.MIN_VALUE);
        int max = Integer.MAX_VALUE;

        for(int i=sequence.length-1;i>-1;i--){

            if(sequence[i]>max) return false;

            while(sequence[i]<roots.peek()){ //这里使用while，栈中存着顶到底 大到小的数据， 非常巧妙，多练几遍。
                max = roots.pop();
            }

            roots.push(sequence[i]);
        }

        return true;
    }
}