Verify Preorder Sequence in Binary Search Tree(Medium)

验证给定序列是否是BST的preoder序列

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.

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

        //将路径中所有小于当前的数pop出来并更新最小值
            while (!stack.isEmpty() && num > stack.peek()) {
                max = stack.pop();
            }

            stack.push(num);
        }

        return true;
}

follow up: 验证post-order

public boolean verifyPostorder(int[] postorder) {
    int ub = Integer.MAX_VALUE;
    Stack<Integer> stk = new Stack<>();
    for (int j = postorder.length - 1; j >= 0; j--) {  // 注意是反过来遍历: left<-right<-root
      if (postorder[j] > ub) return false;
      while (!stk.isEmpty() && postorder[j] < stk.peek()) {
        ub = stk.pop(); // 也可以push到inorder stack里面
      }
      stk.push(postorder[j]);
    }
    return true;
  }

References

1 From Buttercola

2 From SegmentFault

3 postorder sequence