力扣 1008 前序遍历构造二叉搜索树

题意：给定一个二叉搜索树的现需遍历，重构二叉搜索树

思路：先跟遍历数组，每次查看当前遍历到的节点是否在max和min之内，如果不在，返回null，如果在，取当前节点为root，找到其左右子树，返回但前节点

思想：树的先跟遍历

复杂度：时间O（n)，空间O(n)

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        int len = preorder.length;
        if(len == 0)
            return null;
        return build(preorder, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }
    int index = 0;
    TreeNode build(int[] preorder, int max, int min) {
        if(index == preorder.length)
            return null;
        int temp = preorder[index];
        if(temp > max || temp < min)
            return null;
        TreeNode cur = new TreeNode(preorder[index++]);
        cur.left = build(preorder, temp, min);
        cur.right = build(preorder, max, temp);
        return cur;
    }
}