题目描述

递归建立整棵二叉树：先递归创建左右子树，然后创建根节点，并让指针指向两棵子树。

样例

给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7

算法

用dfs算法构建子树。
1. 首先， 把整个前序(pre)数组已经(in)中序数组的索引传入dfs程序。
2. 接着， 找到pre数组的第一个数，这就是剩下所有的子树的根，如果其为空，则返回为0.
3. 如果不为空，那么找到其在中序数组中所在的位置，记为k。
4. 接着遍历地生成左子树以及右子树。
5. 假设本次的pre数组的范围是[pl,pr]，而in数组的范围是[il,ir]。
6. 那么，左子树的pre数组范围是[pl+1,pl+k-il]，因为在左子树的起始点肯定从pl+1开始，而由于是pre前序遍历，前面遍历的肯定都是左子树的，然而现在这个树可能是上一层的右子树，也就是有il个点遍历过了，所以还要遍历k-il个点。
7. 左子树的in数组范围是[il,k-1]，刚好在k号点之前的元素，这个很简单不需要解释。
8. 右子树的pre数组的范围是[pl+k-il+1,pr]，也就是刚好是剩下的那些点。
9. 右子树的in数组的范围是[k+1,ir]，也就是剩下的点。

把边界搞清楚了，编程就很容易了。下面是java代码

时间复杂度分析：blablabla

Java 代码

class Solution {
    int[] preorder;
    int[] inorder;
    HashMap<Integer,Integer> map;
    public TreeNode dfs(int pl, int pr, int il, int ir){
        if(pl > pr) return null;
        TreeNode res = new TreeNode(preorder[pl]);
        int k = map.get(res.val);
        res.left = dfs(pl + 1, pl + k - il, il, k - 1);
        res.right = dfs(pl + k - il + 1, pr, k + 1, ir);
        return res;


    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        map = new HashMap<Integer, Integer>();
        for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);

        return dfs(0, preorder.length-1, 0, inorder.length - 1);
    }
}