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.

Consider the following binary search tree:

 5
/ \

2 6
/
1 3
Example 1:

Input: [5,2,6,1,3]
Output: false
Example 2:

Input: [5,2,1,3,6]
Output: true
Follow up:
Could you do it using only constant space complexity?

我的答案：TLE了

首先看題就懵了，沒看懂什么意思。還是不熟悉BST是什么含義啊。

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) { 
        // edge case, empty input
        return helper(preorder, 0, preorder.size());
    }
    
    bool helper(vector<int>& preorder, int left, int right) {
        if (right-left <= 1)
            return true;
        int root_val = preorder[left];
        int trans_point = right; 
        // init, what if no right branch? -> trans = right -> empty -> true
        for (int i=left+1; i<right; ++i) {
            if (preorder[i] > root_val and trans_point == right) { // unique val
                trans_point = i;
            }
            if (i > trans_point and preorder[i] < root_val)
                return false;
        }
        return helper(preorder, left+1, trans_point) and helper(preorder, trans_point, right);
    }
};

寫的第一版一個問題是，for循環(huán)的第一個if，沒考慮到trans_point第一次變值之后就不用變了

小修補，提升速度的辦法：剪枝
參考https://www.cnblogs.com/grandyang/p/5327635.html的方法3

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) { 
        return helper(preorder, 0, preorder.size(), INT_MIN, INT_MAX);
    }
    
    bool helper(vector<int>& preorder, int left, int right, int lower, int upper) {
        if (right-left < 1)
            return true;
        int root_val = preorder[left];
        if (root_val > upper or root_val < lower)
            return false;
        
        int i=left+1;
        for (; i<right; ++i) {
            if (preorder[i] > root_val) { // unique val
                break;
            }
        }
        
        return helper(preorder, left+1, i, lower, root_val) and helper(preorder, i, right, root_val, upper);
    }
};

Runtime: 852 ms, faster than 16.61% of C++ online submissions for Verify Preorder Sequence in Binary Search Tree.
Memory Usage: 22.9 MB, less than 26.44% of C++ online submissions for Verify Preorder Sequence in Binary Search Tree.

我也嘗試寫過有l(wèi)ower upper的程序，但是沒有提前剪枝，反而更慢了。這里用lower upper和root_val比，替代剪枝掉的判斷是否比trans_point小的功能。不過還是很慢

方法1用stack，https://www.cnblogs.com/grandyang/p/5327635.html

我的寫法：

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) { 
        if (preorder.empty())
            return true;
        
        stack<int> s({preorder[0]});
        int ptr = 1;
        int low = INT_MIN;
        
        while (ptr < preorder.size() and !s.empty()) {
            while (ptr < preorder.size() and preorder[ptr] < s.top()) {
                s.push(preorder[ptr++]);
                if (s.top() < low)
                    return false;
            }
            while (ptr < preorder.size() and !s.empty() and s.top() < preorder[ptr]) {
                low = s.top();
                s.pop();
            }
            if (ptr < preorder.size()) {
                s.push(preorder[ptr++]);                
                if (s.top() < low)
                    return false;
            }
        }
        
        return true;
    }
};

Runtime: 64 ms, faster than 68.46% of C++ online submissions for Verify Preorder Sequence in Binary Search Tree.
Memory Usage: 23.1 MB, less than 12.42% of C++ online submissions for Verify Preorder Sequence in Binary Search Tree.

可以看到中間寫起來非常麻煩，稍不小心就漏一個條件，鏈接里面的寫法就比較簡潔了。while循環(huán)得很注意各種邊界條件，然后一個while循環(huán)里面不同步驟，得仔細(xì)看是否前面會影響后面的邊界。所以還是用for循環(huán)寫一次

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) { 
        if (preorder.empty())
            return true;
        
        stack<int> s;
        int low = INT_MIN;
        
        for (const auto& val : preorder) {
            if (val < low)
                return false;
            
            while (!s.empty() and s.top() < val) {
                low = s.top();
                s.pop();
            }
            
            s.push(val);
        }
        
        return true;
    }
};

Runtime: 64 ms, faster than 68.46% of C++ online submissions for Verify Preorder Sequence in Binary Search Tree.
Memory Usage: 23 MB, less than 17.11% of C++ online submissions for Verify Preorder Sequence in Binary Search Tree.