题目描述

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

注意

二叉树中每个节点的值都互不相同；
输入的前序遍历和中序遍历一定合法；

样例

给定：
前序遍历是：[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

算法

(递归) $O(n)$

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

具体步骤如下：

1. 先利用前序遍历找根节点：前序遍历的第一个数，就是根节点的值；
2. 在中序遍历中找到根节点的位置 kk，则 kk 左边是左子树的中序遍历，右边是右子树的中序遍历；
3. 假设左子树的中序遍历的长度是 ll，则在前序遍历中，根节点后面的 ll 个数，是左子树的前序遍历，剩下的数是右子树的前序遍历；
4. 有了左右子树的前序遍历和中序遍历，我们可以先递归创建出左右子树，然后再创建根节点；

时间复杂度分析

我们在初始化时，用哈希表(unordered_map[HTML_REMOVED])记录每个值在中序遍历中的位置，这样我们在递归到每个节点时，在中序遍历中查找根节点位置的操作，只需要 O(1)的时间。此时，创建每个节点需要的时间是 O(1)，所以总时间复杂度是 O(n)。

Java代码及重要注释

package Head_to_offer_0;

import java.util.HashMap;

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
  }

public class nums6 {
    //思路：根据前序遍历和中序遍历的性质，利用递归的思路不断的划分左右子树，最终进行求解。
    static HashMap<Integer,Integer> pos = new HashMap<>();

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        //特判
        if(preorder == null || preorder.length == 0)
            return null;

        int n = preorder.length;

        //将中序遍历的的数组存入pos中（方便后续的位置查找）
        for(int i = 0;i < n;i ++)
        {
            pos.put(inorder[i],i);
        }

        //递归调用
        return dfs(preorder,inorder,0,n - 1,0,n - 1);
    }

    public static TreeNode dfs(int[] pre,int[] in,int pl,int pr,int il,int ir)
    {
        if(pl > pr) return null;
        int k = pos.get(pre[pl]);
        TreeNode root = new TreeNode(pre[pl]);

        /*边界的确定，
        1）左子树在pre数组上的边界：
        pl的左边界从pl + 1开始很好理解，因为此时已经剔除了pre最左边的元素作为根节点，那么下一个起始位置就是pl + 1；
        向右走过多少位置才是pl的边界呢？因为k取的是根节点在in数组中的位置，可以理解为元素的个数，那么pl从pl + 1开始相应的需要走过
        k - 1个位置后才能在第一个root处取得相同的元素，所以pl + 1 + k - 1，但是要注意的是，这里的k取得是in数组中从0开始的位置，
        相加后，一定会重复前面的一段，所以需要还需要减去il，这里il理解为左子树在in数组左边界的位置，那么pl的右边界可以写作pl + 1 + k - 1 - il
        2）左子树在in数组上的边界：从il开始，到k - 1，比较好理解
        3）右子树在pre数组上的边界：
        由1）知此时左边界为右边界 + 1，即pl + 1 + k - 1 - il + 1，右边界为pr
        4）右子树在in数组上的边界：从k + 1开始，到ir，比较好理解
        */
        root.left = dfs(pre,in,pl + 1,pl + 1 + k - 1 - il,il,k - 1);
        root.right = dfs(pre,in,pl + k - il + 1,pr,k + 1,ir);
        return root;
    }

    public static void main(String[] args)
    {
        int[] preorder = {1,2,4,7,3,5,6,8};
        int[] inorder = {4,7,2,1,5,3,8,6};
        System.out.println(buildTree(preorder,inorder));
    }
}