Leetcode: Verify Preorder Sequence in Binary Search Tree

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?

Brute-force solution:
The idea to solve the problem is: a[0] must be the root of the BST. Then we start from index 1 and iterate until a number which is greater than root, mark as i. All the numbers less than i must be less than root, number greater than i must be greater than root. Then we can recursively validate the BST.

先复习一下BST，给定一个节点，其左子树的所有节点都小于该节点，右子树的所有节点都大于该节点；preorder序列是指在遍历该BST的时候，先记录根节点，再遍历左子树，然后遍历右子树；所以一个preorder序列有这样一个特点，左子树的序列必定都在右子树的序列之前；并且左子树的序列必定都小于根节点，右子树的序列都大于根节点；

根据上面的特点很容易通过递归的方式完成：

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

Code (Java):

public class Solution {
    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);
    }
}

Analysis:
Time complexity O(n^2), space complexity O(1). 


Solution using two stacks:
http://segmentfault.com/a/1190000003874375

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. 

Code (Java):

public class Solution {
    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;
    }
}

Solution using one stack:
Since the in-order list only stores the number in ascending order. We can use a variable to store only the last i.e max value. 

Code (Java):

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) {
            return true;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        int max = Integer.MIN_VALUE;
        
        for (int num : preorder) {
            if (num < max) {
                return false;
            }
            
            while (!stack.isEmpty() && num > stack.peek()) {
                max = stack.pop();
            }
            
            stack.push(num);
        }
        
        return true;
    }
}

A constant-space solution:

public class Solution {
    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;
    }
}