题解 | #重建二叉树#

方法一（递归+哈希表）

1.题意整理

给定一颗二叉树的前序遍历序列和中序遍历序列。
重建该二叉树，并返回头节点。

2.思路整理

因为前序遍历是按根、左、右的顺序访问节点，中序遍历是按左、根、右的顺序访问节点。一个朴素的思路是，先找到前序序列的第一个元素，将其作为头节点，然后通过遍历中序序列，找到中序序列对应的头节点位置，则中序序列中该位置之前的一定是当前节点的左子树部分，该位置之后的一定是当前节点的右子树部分。知道了左右子树的节点个数，我们便可以推导出前序序列中左右子树的分界点。这样我们便可以构建当前节点的左右子树，通过递归的方式，便可以构建出树中每一个节点。

上面的思路中是通过遍历中序序列找到对应当前节点的位置，由于每次递归都需要搜索整个中序序列，时间复杂度较高，我们可以在递归之前对中序序列进行预处理，将中序序列的值与索引之间的映射加入到dic哈希表，然后递归的过程中直接从dic取出来即可。

递归终止条件：前序、中序中任意一个序列走完，递归就会终止。
递归如何传递：首先通过dic找到中序序列左右子树分界点，得到左右子树节点个数，进而可以推算出前序序列分界点。从而可以确定当前节点的左右子树。
递归的返回值：返回当前节点为根的子树。

图解展示：

alt

3.代码实现

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    //记录中序序列的值与索引之间的映射
    HashMap<Integer,Integer> dic=new HashMap<>();
    
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        //将中序序列对应的映射加入到dic
        for(int i=0;i<vin.length;i++){
            dic.put(vin[i],i);
        }
        TreeNode root=createTree(pre,0,pre.length-1,vin,0,vin.length-1);
        return root;
    }
    
    private TreeNode createTree(int[] pre,int prestart,int preend,int[] vin,int vinstart,int vinend){
        //递归终止条件
        if(prestart>preend||vinstart>vinend){
            return null;
        }
        //新建当前节点
        TreeNode root=new TreeNode(pre[prestart]);
        //从dic字典中取出值为pre[prestart]的索引
        int i=dic.get(pre[prestart]);
        //确定当前节点的左右子节点
        root.left=createTree(pre,prestart+1,prestart+i-vinstart,vin,vinstart,i-1);
        root.right=createTree(pre,prestart+i-vinstart+1,preend,vin,i+1,vinend);
        //返回当前节点对应的子树
        return root;
    }
}

4.复杂度分析

时间复杂度：需要重建二叉树中所有节点，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外深度为n的递归栈开销和长度为n的哈希表，所以空间复杂度为 $O (n)$ 。