255. Verify Preorder Sequence in Binary Search Tree - cocoder39/coco39_LC GitHub Wiki

Maintain a monotonically decreasing stack. Then the stack would store a node and its left child, left child of left child...

              6
            /  \  
           3    7
          /  \
         1   5
         \   /
         2  4

6, 3, 1 would be pushed into stack one by one. when visiting 2, we found 2 is greater than top of stack which is 1. Thus 2 has to be the root of right subtree of a visited node. all nodes less than 2 would be popped out, and only 6, 3 left in stack. Then 2 would be pushed into stack. Hence, stack stores 6, 3, 2. we can view the bst as

              6
            /  \  
           3    7
          /  \
         2   5
             /
            4

also keep in mind that all the following nodes in the subtree rooted with 2 should be greater than 1, which is root of previous subtree.

Solution 1 : time is O(n) and space is O(height) since only maintain a root-to-leave path

bool verifyPreorder(vector<int>& preorder) {
        stack<int> s;
        int low = INT_MIN;
        
        for (int i = 0; i < preorder.size(); i++) {
            if (preorder[i] < low) {
                return false;
            }
            
            while (! s.empty() && preorder[i] > s.top()) {
                low = s.top();
                s.pop();
            }
            s.push(preorder[i]);
        }
        return true;
    }

solution 2: use existing vector preorder to mimic stack, achieving O(1) space

bool verifyPreorder(vector<int>& preorder) {
        int low = INT_MIN;
        int top = -1; //mimic top index of stack
        for (int i = 0; i < preorder.size(); i++) {
            if (preorder[i] < low) {
                return false;
            }
            
            while (top >= 0 && preorder[i] > preorder[top]) {
                low = preorder[top--];
            }
            preorder[++top] = preorder[i];
        }
        return true;
    }

follow up: verify post order sequence in bst. scan from right to left of the given sequence, maintain a monotonically increasing stack.

             3
            /  \  
           1    7
               /  \
              4   9
              \   /
               5  8
postorder: 1, 5, 4, 8, 9, 7, 3
stack: 
3, 7, 9
3, 7, 8 (upper bound 9)
3, 4, 5 (upper bound 7)
1       (upper bound 3)

upper bound is the last element popped out.

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;
    }
⚠️ **GitHub.com Fallback** ⚠️