FB 面经 Preorder to Binary Search

常规思路是第一个为根，然后找到第一个大于他和第一个小于他的数，这两个分别为新的两个根，call 递归， O(n^2)

下面则是tricky 利用全局变量做法 O（n)

int index = 0;
  static TreeNode convert(int[] pre, int min, int max) {
    if (index >= pre.length) {
      return null;
    }
    if (pre[index] <= min || pre[index] >= max) {
      return null;
    }
    TreeNode root = pre[index++];
    root.left = convert(pre, min, root.val);
    root.right = convert(pre, root.val, max);
    return root;
  }