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

请设置文章作者

发布于：2020年7月15日

次浏览

题目链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/

一、题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

1
2

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

限制：

1

0 <= 节点个数 <= 5000

二、题目解析

首先，我们先来复习一下前序遍历、中序遍历。（在下方的视频中分布讲解）

前序遍历

二叉树的前序遍历顺序是：根节点、左子树、右子树，每个子树的遍历顺序同样满足前序遍历顺序。

中序遍历

二叉树的中序遍历顺序是：左子树、根节点、右子树，每个子树的遍历顺序同样满足中序遍历顺序。

复习过后，我们可以得出以下结论：

• 在二叉树的 前序遍历 序列中，第一个数字总是树的根结点的值；
• 在二叉树的 中序遍历 序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边

以本题的序列为例，前序遍历序列的第一个数字 3 就是根结点的值，在中序遍历序列，找到根结点值的位置。根据中序遍历特点，在根结点的值 3 前面的数字都是左子树结点的值，在根结点的值 3 后面的数字都是右子树结点的值。

二叉树很重要的一个性质是递归，在找到了左子树、右子树的前序遍历序列和中序遍历序列后，我们可以按照同样的方法去确定 子左子树 和 子右子树 的构建。

具体的代码编写思路如下（来源于 Krahets’s Blog）：

• 递推参数： 前序遍历中根节点的索引pre_root_idx、中序遍历左边界in_left_idx、中序遍历右边界in_right_idx。
• 终止条件： 当 in_left_idx > in_right_idx ，子树中序遍历为空，说明已经越过叶子节点，此时返回 null 。
• 递推工作：

1. 建立根节点 root ： 值为前序遍历中索引为pre_root_idx的节点值。

2. 搜索根节点 root 在中序遍历的索引 i ： 为了提升搜索效率，本题解使用哈希表 map 预存储中序遍历的值与索引的映射关系，每次搜索的时间复杂度为 O(1)。

3. 构建根节点 root的左子树和右子树：通过调用 recursive() 方法开启下一层递归。

4. • 左子树： 根节点索引为 pre_root_idx + 1 ，中序遍历的左右边界分别为 in_left_idx 和 i - 1。
   • 右子树： 根节点索引为 i - in_left_idx + pre_root_idx + 1（即：根节点索引 + 左子树长度 + 1），中序遍历的左右边界分别为 i + 1 和 in_right_idx。

• 返回值： 返回 root，含义是当前递归层级建立的根节点 root 为上一递归层级的根节点的左或右子节点。

三、动画描述

四、图片描述

五、参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    //在中序序列中查找与前序序列首结点相同元素的时候，如果使用 while 循环去一个个找效率很慢
    //这里我们借助数据结构 HashMap 来辅助查找，在开始递归之前把所有的中序序列的元素和它们所在的下标存到一个 map 中，这样查找的时间复杂度是 O(logn)
    HashMap<Integer, Integer> map = new HashMap<>();

    //保留的前序遍历
    int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        //在开始递归之前把所有的中序序列的元素和它们所在的下标存�