LeetCode 255 - Verify Preorder Sequence in Binary Search Tree

https://segmentfault.com/a/1190000003874375

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up: Could you do it using only constant space complexity?

遍历这个序列，一旦出现先后的两个元素 a<b，说明a、b是同一个某左子树上的升序排列。之后出现的任何元素相对于a来说一定都是右子树元素，必定要比a大，任何c<a的情况都是不合法的。

于是本题转化为：如何在遍历preorder的过程中，不断更新a<b，使得a不断得以抬升（当前所有a<b的pair中最大的a），一旦出现后续的c<a即可宣告false

怎么维护一个最新（尽量大）的a<b呢？那就是用栈来维护一个递减的序列。一旦遍历的过程中出现了 preOrder[i]>Stack.top()，那就说明出现了递增序列，需要不断退栈直至保证栈本身仍然是递减的。在退栈的过程中，就不断遇到a<b的情况，借机可以抬高a

http://shibaili.blogspot.com/2019/02/255-verify-preorder-sequence-in-binary.html
stack里保证的是递增（从top到底下），遇到比top大说明是走到了右子树，然后把之前左子树跟root全部pop掉，取root为lower bound（之后再也不会遇到比这更小，如果有，说明顺序有错误）
http://www.cnblogs.com/grandyang/p/5327635.html

这道题让给了我们一个一维数组，让我们验证其是否为一个二叉搜索树的先序遍历出的顺序，我们都知道二叉搜索树的性质是左<根<右，如果用中序遍历得到的结果就是有序数组，而先序遍历的结果就不是有序数组了，但是难道一点规律都没有了吗，其实规律还是有的，根据二叉搜索树的性质，当前节点的值一定大于其左子树中任何一个节点值，而且其右子树中的任何一个节点值都不能小于当前节点值，那么我们可以用这个性质来验证，举个例子，比如下面这棵二叉搜索树：

     5
    / \
   2   6
  / \
 1   3

其先序遍历的结果是{5, 2, 1, 3, 6}, 我们先设一个最小值low，然后遍历数组，如果当前值小于这个最小值low，返回false，对于根节点，我们将其压入栈中，然后往后遍历，如果遇到的数字比栈顶元素小，说明是其左子树的点，继续压入栈中，直到遇到的数字比栈顶元素大，那么就是右边的值了，我们需要找到是哪个节点的右子树，所以我们更新low值并删掉栈顶元素，然后继续和下一个栈顶元素比较，如果还是大于，则继续更新low值和删掉栈顶，直到栈为空或者当前栈顶元素大于当前值停止，压入当前值，这样如果遍历完整个数组之前都没有返回false的话，最后返回true即可

二叉搜索树先序遍历序列的特点是降序的部分一定是向左走的，一旦开始升序说明开始向右走了，则上一个降序的点则限定了后面的数的最小值。如果继续降序，说明又向左走了，这样等到下次向右走得时候也要再次更新最小值

    10
   /  \
  5    12
 / \
2   6

如这个例子，我们在10的位置是没有最小值限定的，然后降序走到5，依然没有最小值，降序走到2，依然没有，然后开始升序了，遇到6，这时候之后的数字一定大于2，同时也大于5，所以最小值更新为之前遍历过的，且比当前数稍微小一点的那个数。这里我们可以用一个栈来暂存之前的路径，所以升序时就是将栈中元素不断pop出来直到栈顶大于当前数，而最小值就是最后一个pop出来的数，最后再把该数push进去。对于降序的时候，直接向里面push就行了。这样，序列无效的条件就是违反了这个最小值的限定。

    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> stk = new Stack<Integer>();
        // 初始化最小值为最小整数
        int min = Integer.MIN_VALUE;
        for(int num : preorder){
            // 违反最小值限定则是无效的
            if(num < min) return false;
            // 将路径中所有小于当前的数pop出来并更新最小值
            while(!stk.isEmpty() && num > stk.peek()){
                min = stk.pop();
            }
            // 将当前值push进去
            stk.push(num);
        }
        return true;
    }

https://blog.csdn.net/qq508618087/article/details/50929129
对于一个搜索二叉树的前序序列来说, 如果某段序列为一个递减序列, 说明这是一段沿着左子树的路径. 直到碰到一个比前一个大的值, 说明此时已经来到某个结点的右子树上了, 而此时可以得出一个此后序列的下界值, 也就是此后序列的任意一个值必须要比这个结点的父结点的值大, 因为对于搜索二叉树来说根节点左边的都比根节点小, 而根节点右边的都比根节点大, 所以既然现在已经来到某个结点(设为A)的右子树上, 那么此后任何结点的值必然比A的值大.

那么当我们碰到一个比之前结点大的值如何找到他的父结点呢? 可以借助一个栈, 即如果当前结点比栈顶元素小, 就入栈, 如果当前值大于栈顶值, 则让所有比当前结点小的值都出栈, 直到栈顶元素比当前结点大, 则最后一个出栈的比当前结点小的值就是当前结点的父结点, 我们只要在栈元素出栈的时候更新最小下界再将当前元素入栈即可. 另外这样的时间和空间复杂度都是O(n), 但是对于空间复杂度来说, 很容易复用原数组模拟栈来优化

X.
https://discuss.leetcode.com/topic/21217/java-o-n-and-o-1-extra-space
http://zhongshutime.com/2017/leetcode_255/

Kinda simulate the traversal, keeping a stack of nodes (just their values) of which we're still in the left subtree. If the next number is smaller than the last stack value, then we're still in the left subtree of all stack nodes, so just push the new one onto the stack. But before that, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, in the right subtree of an ancestor). Also, use the popped values as a lower bound, since being in their right subtree means we must never come across a smaller number anymore.

public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE;
    Stack<Integer> path = new Stack();
    for (int p : preorder) {
        if (p < low)
            return false;
        while (!path.empty() && p > path.peek())
            low = path.pop();
        path.push(p);
    }
    return true;
}

Solution 2 ... O(1) extra space

Same as above, but abusing the given array for the stack.

public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE, i = -1;
    for (int p : preorder) {
        if (p < low)
            return false;
        while (i >= 0 && p > preorder[i])
            low = preorder[i--];
        preorder[++i] = p;
    }
    return true;
}

http://www.nowtoshare.com/en/Article/Index/20293
    public boolean verifyPreorder(int[] preorder) {         if(preorder.length==0) return true;         Stack<Integer> stack=new Stack<Integer>();         stack.push(preorder[0]);         int leftBound=Integer.MIN_VALUE;         for(int i=1;i<preorder.length;i++)         {           //  System.out.println(stack);             if(preorder[i]<stack.peek())             {                 if(preorder[i]<leftBound) return false;                 //sink                  stack.push(preorder[i]);             }             else{                 //swim                while(!stack.isEmpty() &&stack.peek()<preorder[i])                {                  leftBound=stack.pop();                }                stack.push(preorder[i]);             }         }         return true;     }


X. A constant-space solution:

    10
   /  \
  5    12
 / \
2   6

同样是看这个例子，我们序列是[10, 5, 2, 6, 12]，如果用栈的话，遍历序列到第n个数时，栈中的情况是这样的：

1 | 10
2 | 10 5
3 | 10 5 2
4 | 10 6
5 | 12

可见我们栈的大小是不会超过我们当前遍历的数的位置的，所以我们大可以用该序列的之前遍历过的部分来当做我们的栈。这里用一个i指针标记栈顶。

注意

这里栈顶指针应初始化为-1，这样栈第一个元素加入时，i++后不会超界

    public boolean verifyPreorder(int[] preorder) {
        // 用i标记栈顶
        int i = -1, min = Integer.MIN_VALUE;
        for(int num : preorder){
            if(num < min) return false;
            // 同样的解法，但是复用了数组作为栈，每pop一次相当于i--
            while(i >= 0 && num > preorder[i]){
                min = preorder[i--];
            }
            // push相当于i++
            preorder[++i] = num;
        }
        return true;
    }

    public boolean verifyPreorder(int[] preorder) {

        if (preorder == null || preorder.length <= 1) {

            return true;

        }

         

        int i = -1;

        int max = Integer.MIN_VALUE;

         

        for (int num : preorder) {

            if (num < max) {

                return false;

            }

             

            while (i >= 0 && num > preorder[i]) {

                max = preorder[i];

                i--;

            }

             

            i++;

            preorder[i] = num;

        }

         

        return true;

    }

X. Using 2 stacks
http://ftalm.blogspot.com/2015/11/leetcode-verify-preorder-sequence-in.html

    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> inorder = new Stack<Integer>();
        Stack<Integer> temp = new Stack<Integer>();
        
        for (int i = 0; i < preorder.length; i++){
            if (!inorder.isEmpty()&&preorder[i] < inorder.peek()){
                return false;
            }
            while (!temp.isEmpty() && temp.peek() < preorder[i]){
                inorder.push(temp.pop());
            }
            temp.push(preorder[i]);
        }
        return true;
    }

http://buttercola.blogspot.com/2015/09/leetcode-verify-preorder-sequence-in.html
Use a stack to store the numbers less than num, and a list to store the numbers in an ascending order. If the in-order list descends, return false. 

    public boolean verifyPreorder(int[] preorder) {

        if (preorder == null || preorder.length <= 1) {

            return true;

        }

         

        Stack<Integer> stack = new Stack<Integer>();

        List<Integer> list = new ArrayList<>();

         

        for (int num : preorder) {

            if (!list.isEmpty() && num < list.get(list.size() - 1)) {

                return false;

            }

             

            while (!stack.isEmpty() && num > stack.peek()) {

                list.add(stack.pop());

            }

             

            stack.push(num);

        }

         

        return true;

    }

X. O(N^2)
http://buttercola.blogspot.com/2015/09/leetcode-verify-preorder-sequence-in.html
Time complexity O(n^2), space complexity O(1). 

1. 如果序列只有一个元素，那么肯定是正确的，对应只有一个节点的树；
2. 如果多于一个元素，以当前节点为根节点；并从当前节点向后遍历，直到大于根节点的节点出现（或者到尾巴），那么根节点之后，该大节点之前的，是左子树；该大节点及之后的组成右子树；递归判断左右子树即可；
3. 那么什么时候一个序列肯定不是一个preorder序列呢？前面得到的右子树，如果在其中出现了比根节点还小的数，那么就可以直接返回false了；

    public boolean verifyPreorder(int[] preorder) {

        if (preorder == null || preorder.length <= 1) {

            return true;

        }

         

        return verifyPreorderHelper(preorder, 0, preorder.length - 1);

    }

     

    private boolean verifyPreorderHelper(int[] preorder, int lo, int hi) {

        if (lo >= hi) {

            return true;

        }

         

        int root = preorder[lo];

        int i = lo + 1;

        while (i <= hi && preorder[i] < root) {

            i++;

        }

         

        int j = i;

        while (j <= hi && preorder[j] > root) {

            j++;

        }

         

        if (j <= hi) {

            return false;

        }

         

        return verifyPreorderHelper(preorder, lo + 1, i - 1) &&

               verifyPreorderHelper(preorder, i, hi);

    }

http://leetcode0.blogspot.com/2015/12/255-verify-preorder-sequence-in-binary.html

    public boolean verifyPreorder(int[] preorder) {

        return helper(preorder,0,preorder.length-1);

    }

    private boolean helper(int[] preorder, int start, int end){

        if(start >= end)

            return true;

        // find the first that is less than

        int val = preorder[start];

        int i = start+1;

        while(i<=end && preorder[i]<val)

            i++;

        for(int j = i ; j<=end; j++){

            if(preorder[j]<val)

                return false;

        }

        return helper(preorder, start+1,i-1) && helper(preorder,i,end);

    }

https://discuss.leetcode.com/topic/21216/divide-conquer-java-solution

public boolean verifyPreorder(int[] preorder) {
    return verify(preorder, 0, preorder.length - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private boolean verify(int[] preorder, int start, int end, int min, int max) {
    if (start > end) {
        return true;
    }
    int root = preorder[start];
    if (root > max || root < min) {
        return false;
    }
    
    int rightIndex = start;
    while (rightIndex <= end && preorder[rightIndex] <= root) {
        rightIndex++;
    }
    return verify(preorder, start + 1, rightIndex - 1, min, root) && verify(preorder, rightIndex, end, root, max);
}

X.
https://discuss.leetcode.com/topic/21216/divide-conquer-java-solution

Recursively examine every key in the array. For each BST node, its key must be greater than all keys in left subtree and less than keys in right subtree.

Since given preorder sequence, the first element is always the root. Partition the array by the key of root, find the index of the first number greater than it.

Base case:

1. start index exceeds end index, the array to be checked is empty, return true;
2. root key is not within upper and lower boundaries, return false.

X. O(N^2)
http://www.nowtoshare.com/en/Article/Index/20293

O(1) Space, but slow

public boolean verifyPreorder(int[] preorder) { if(preorder.length==0) return true; int lastPos=0; int leftBound=Integer.MIN_VALUE; for(int i=1;i<preorder.length;i++) { // System.out.println(stack); if(preorder[i]<preorder[lastPos]) { if(preorder[i]<leftBound) return false; //sink lastPos=i; } else{ //swim for(int k=lastPos;k>=0;k--) { if(preorder[k]>preorder[i]) break; leftBound=Math.max(leftBound,preorder[k]); } lastPos=i; } } return true; }
https://github.com/wisdompeak/LeetCode/tree/master/Tree/255.Verify-Preorder-Sequence-in-Binary-Search-Tree

根据preorder的首元素（根节点）通过大小的比较，将后续元素分为属于其左子树和右子树的子区间，分别递归调用

bool DFS(vector<int>& preorder, int start, int end)。

边界条件：到end-start<=1时，就可以返回true

注意到，第一轮遍历判定左子树之后，还需要在第二轮对该左子树的左子树再做一回遍历比较，不断递归，有相当多的重复计算量。此题最坏情况下需要o(n^2)的时间复杂度，会非常慢。

    bool verifyPreorder(vector<int>& preorder) 
    {
        return DFS(preorder,0,preorder.size()-1);
    }
    
    bool DFS(vector<int>& preorder, int start, int end)
    {
        if (end-start<=1) return true;
        
        int root=preorder[start];
        int i=start;
        while (preorder[i+1]<root && i+1<=end) i++;
        int mid=i+1;
        i=mid;
        while (i<=end)
        {
            if (preorder[i]<=root)
                return false;
            i++;    
        }
        return DFS(preorder,start+1,mid-1)&&DFS(preorder,mid,end);
    }

X. Follow up
Q：如何验证中序序列？
A：中序序列是有序的，只要验证其是否升序的就行了。

Q：如何验证后序序列？
A：后序序列的顺序是left - right - root，而先序的顺序是root - left - right。我们同样可以用本题的方法解，不过是从数组的后面向前面遍历，因为root在后面了。而且因为从后往前看是先遇到right再遇到left，所以我们要记录的是限定的最大值，而不再是最小值，栈pop的条件也变成pop所有比当前数大得数。栈的增长方向也是从高向低了。

    public boolean IsValidPostOrderBst(int[] nums)
    {
        int i = nums.length;
        int max = Integer.MAX_VALUE;
        for (int j = nums.length - 1; j >= 0; j--)
        {
            if (nums[j] > max) return false;
            while (i <= nums.length - 1 && nums[j] > nums[i])
                max = nums[i++];
            nums[--i] = nums[j];
        }
        return true;
    }