本题乍一看难度有点高，其实真的不难，事实上也用divide & conquer的方法做出了，只是那种方法太烂了。所以用Stack又重新写了一遍，虽然不符合Follow Up里面的最高要求，但是我觉得对于面试是足够了

    • preorder的顺序是parent -> left -> right
    • 但是通过Stack，我们可以把顺序转化为inorder: left-> parent-> right：即从Stack中pop()出来的顺序

    • 这个顺序应该是单调递增，

      • 或者说换种说法：只要能用通过rule转化成inorder，并且这个inorder是单调递增，则说明是valid的

    • 时间复杂度：255. Verify Preorder Sequence in Binary Search Tree - 图1

    • 空间复杂度：255. Verify Preorder Sequence in Binary Search Tree - 图2

    代码如下 :

    1. class Solution {
    2.   public boolean verifyPreorder(int[] preorder) {
    3.     if (preorder == null || preorder.length == 0) {
    4.       return true;
    5.     }
    6.     int min = Integer.MIN_VALUE;
    8.     for (int i = 0; i < preorder.length; ++i) {
    9.       if (preorder[i] < min) {
    10.         return false;
    11.       }
    13.       if (stack.isEmpty() || preorder[i] < preorder[i-1]) {
    14.         // left
    15.         stack.push(preorder[i]);
    16.       }
    17.       else {
    18.         // right
    19.         while (!stack.isEmpty() && stack.peek() < preorder[i]) {
    20.           // pop out all the nodes(left sibling + parent) small than new node
    21.           min = stack.pop(); // all the node should be smaller than this one
    22.         }
    23.         stack.push(preorder[i]);
    24.       }
    25.     }
    27.     return true;
    28.   }
    29. }