388，先序遍历构造二叉树

Love is the one thing that transcends time and space. 

只有爱可以穿越时空。

问题描述

返回与给定先序遍历相匹配的二叉搜索树的根结点。

示例：

输入：[8，5，1，7，10，12]

输出：[8，5，10，1，7，null，12]

问题分析

我们知道先序遍历的顺序是：根节点→左子树→右子树。二叉搜索树的特点是当前节点左子树的值都小于当前节点，当前节点右子树的值都大于当前节点。比如我们在下面的搜索二叉树中插入节点4

原理很简单，我们来看下如果插入一个结点的时候代码该怎么写

 1//data是插入的结点
 2private static void addTreeNode(TreeNode root, int data) {
 3    TreeNode node = new TreeNode(data);
 4    TreeNode p = root;
 5    while (true) {
 6        //如果要插入的结点data比结点p的值小，就往p结点的左
 7        //子节点找，否则往p的右子节点找
 8        if (p.val > data) {
 9            //如果p的左子节点等于空，直接放进去
10            if (p.left == null) {
11                p.left = node;
12                break;
13            } else {
14                p = p.left;
15            }
16        } else {
17            //如果p的右子节点等于空，直接放进去
18            if (p.right == null) {
19                p.right = node;
20                break;
21            } else {
22                p = p.right;
23            }
24        }
25    }
26}

上面代码很简单，插入一个结点的代码写出来了，我们只需要把数组中的元素全部遍历一遍然后再一个个插入即可，代码如下

1public TreeNode bstFromPreorder(int[] preorder) {
2    TreeNode root = new TreeNode();
3    root.val = preorder[0];
4    for (int i = 1; i < preorder.length; i++)
5        addTreeNode(root, preorder[i]);
6    return root;
7}

递归方式

上面节点插入的时候我们使用的是while循环的方式，这种比较容易理解，但代码量相对比较多，我们还可以改为递归的方式

1private TreeNode addTreeNode(TreeNode root, int val) {
2    if (root == null)
3        return new TreeNode(val);
4    else if (root.val > val)
5        root.left = addTreeNode(root.left, val);
6    else
7        root.right = addTreeNode(root.right, val);
8    return root;
9}

这种递归的方式代码会更简洁一些。如果root为空的话会新建一个节点。否则会一直走下去，他会根据root节点的大小判断往左走还是往右走，注意这里的root节点不一定是根节点，在递归的时候他是一直变的。

二分法构造

我们知道输入的数据是二叉树的先序遍历，那么第一个节点肯定是头结点，比他小的是他左子树的节点值，比他大的是他右子树的节点值，我们就拿上面的[8,5,1,7,10,12]来说，8是根节点，比8小的[5，1，7]是他左子树上的值，比他大的[10，12]是他右子树上的值。所以可以参照二分法查找的方式，把数组分为两部分，他是这样的

然后左边的[5，1，7]我们再按照上面的方式拆分，5是根节点，比5小的1是左子节点，比5大的7是右子节点。同理右边的[10，12]中10是根节点，比10大的12是右子节点，这样我们一直拆分下去，直到不能拆分为止，所以结果是下面这样

我们再来看下代码

 1public TreeNode bstFromPreorder(int[] preorder) {
 2    return buildBST(preorder, 0, preorder.length - 1);
 3}
 4
 5//数组的范围从left到right
 6private TreeNode buildBST(int[] preorder, int left, int right) {
 7    if (left > right)
 8        return null;
 9    TreeNode root = new TreeNode(preorder[left]);
10    //如果left==right说明只有一个元素，没法再拆分了
11    if (left == right)
12        return root;
13    int i = left;
14    //拆分为两部分，一部分是比preorder[left]大的，一部分是比preorder[left]小的
15    while (i + 1 <= right && preorder[i + 1] < preorder[left])
16        i++;
17    //区间[left + 1，i]所有元素都在root节点的左子树
18    //区间[i + 1，right]所有元素都在root节点的右子树
19    root.left = buildBST(preorder, left + 1, i);
20    root.right = buildBST(preorder, i + 1, right);
21    return root;
22}

先序遍历

我们还可以参照先序遍历的方式把数组元素一个个取出来，也很好理解，直接上代码。

 1int index = 0;
 2
 3public TreeNode bstFromPreorder(int[] preorder) {
 4    return bstFromPreorder(preorder, Integer.MAX_VALUE);
 5}
 6
 7public TreeNode bstFromPreorder(int[] preorder, int max) {
 8    if (index == preorder.length || preorder[index] > max)
 9        return null;
10    //把数组中的元素一个个取出来创建节点
11    TreeNode root = new TreeNode(preorder[index++]);
12    //左子树的最大值不能超过root.val
13    root.left = bstFromPreorder(preorder, root.val);
14    //右子树的最大值不能超过max
15    root.right = bstFromPreorder(preorder, max);
16    return root;
17}

使用栈来解决

这题解法比较多，再来看最后一种解题思路。我们还可以使用一个栈来维护二叉搜索树中的节点，栈中存放的是已经构建好的二叉搜索树的结点（但不是全部，有些可能已经出栈了），其中栈中元素从栈底到栈顶是递减的，我们遍历数组的时候如果当前值小于栈顶元素的值，我们直接让当前值成为栈顶元素节点的左子节点，然后压栈。

1        if (preorder[i] < stack.peek().val) {
2               stack.peek().left = node;
3        } 

如果当前元素的值大于栈顶元素的值，我们就让栈顶元素出栈，直到当前元素的值小于栈顶元素的值为止（或者栈为空为止）。而前一个比当前元素值小的节点就是当前元素的父节点。而当前元素是他父节点的右子节点。

1            TreeNode parent = stack.peek();
2            //栈从栈底到栈顶是递减的
3            while (!stack.isEmpty() && preorder[i] > stack.peek().val) {
4                   parent = stack.pop();
5            }
6            parent.right = node;

解惑：

这里如果思路不是很清晰的可能会有点疑问，出栈的时候把小于当前元素的值出栈了，如果再遇到比出栈的元素还要小的值那不是完蛋了，因为那个值已经出栈了，找不到了。其实有这个想法是正确的，但这种想法有点多余了，我们就拿下面的图来说吧[8,5,1,7,10,12]

比如当我们插入节点7的时候，节点1，5都已经全部出栈，但7后面无论如何都不会再出现比1或者5还小的值了，因为他是二叉搜索树，5的右节点的所有值都是比5大的。我们来画个简单的图看下

所以我们看到后面无论走到哪一步都不可能在遇到比出栈元素更小的值了，最后我们再来看下完整代码

 1public TreeNode bstFromPreorder(int[] preorder) {
 2    Stack<TreeNode> stack = new Stack<>();
 3    TreeNode root = new TreeNode(preorder[0]);
 4    stack.push(root);
 5    for (int i = 1; i < preorder.length; i++) {
 6        TreeNode node = new TreeNode(preorder[i]);
 7        //小于栈顶元素的值，说明应该在栈顶元素的左子树
 8        if (preorder[i] < stack.peek().val) {
 9            stack.peek().left = node;
10        } else {//大于栈顶元素的值，我们要找到当前元素的父节点
11            TreeNode parent = stack.peek();
12            //栈从栈底到栈顶是递减的
13            while (!stack.isEmpty() && preorder[i] > stack.peek().val) {
14                parent = stack.pop();
15            }
16            parent.right = node;
17        }
18        //节点压栈
19        stack.push(node);
20    }
21    return root;
22}

●374，二叉树的最小深度

●373，数据结构-6,树

●372，二叉树的最近公共祖先

●367，二叉树的最大深度