255. Verify Preorder Sequence in Binary Search Tree

一刷。

这个题发现笔记里没有，只能从LC的存档里找到一刷的做法。
其中while loop是模拟从左志往回到root的过程，最后记录ROOT，就是sub tree的最大值，并且要保证当前subTree的ROOT要小于接下来右支的traversal的所有值。

说白了是用Stack模拟了per-order的过程。

Time : O(n)
Space : O(n)

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

感觉挺难的，不知道当时怎么想的。

---

二刷。

二刷是递归做的， 每次把array分成3部分，num[0]是subRoot，然后往后只要小于nums[0]就是坐支，从大于num[0]开始到最后是右支。
分完了别忘看看是不是右支所有都大于nums[0]

然后递归左右支。

Time : O(NlgN)
Space : O(NlgN) ? 算上memory stack的话。 不算是O(1)

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder.length == 0) return true;
        return helper(preorder, 0, preorder.length - 1);
    }
    
    public boolean helper(int[] nums, int l, int r) {
        if (r - l <= 1) {
            return true;
        } 
        int mid = r + 1;
        int rootVal = nums[l];
        
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] > rootVal) {
                mid = i;
                break;
            } 
        }
        
        for (int i = mid; i <= r; i++) {
            if (nums[i] <= rootVal) {
                return false;
            }
        }
        return helper(nums, l + 1, mid - 1) && helper(nums, mid, r);
    }
}

有个O(n), O(1)的办法。。。
来自大名鼎鼎的StefanPochmann

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;
}

有点厉害，不过这个德国逼的缺点就是太追求代码的简短，经常弄个1行2行的看着怪恶心的。

可能这就是他为毛喜欢写Python的原因，短。不过有时候可读性非常差。