LeetCode题目：重建二叉树

题目描述：

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

例如，给出

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

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

返回如下的二叉树：

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

LeetCode的题解里面有这道题很详细的解析，但是仍然需要说明一下，起码是我看起来有点吃力的地方：

1、TreeNode本身在软件里面是一个接口（我用的是Eclipse 1.8），所以照着题目里面TreeNode的自定义类输入，是无法实例化的，必须要改个名字（我改成了TreeNode1）。

2、要注意里面位置的描述：in_left，in_right是在说中序遍历里面的左子树和右子树的边界，左子树边界in_left到根节点之间的节点是左子树包含的节点，根节点到右子树边界之间的节点是右子树包含的节点。

3、回溯里面的思想是将左子树和右子树的第一个节点作为根节点，这样后面跟着的又是一个二叉树，只是新的二叉树的左右边界有所改变。

题目分析：

前序遍历特点： 节点按照

[ 根节点 | 左子树 | 右子树 ]

排序，以题目示例为例：

[ 3 | 9 | 20 15 7 ]

中序遍历特点： 节点按照

[ 左子树 | 根节点 | 右子树 ]

排序，以题目示例为例：

[ 9 | 3 | 15 20 7 ]

根据题目描述

输入的前序遍历和中序遍历的结果中都不含重复的数字

，其表明树中每个节点值都是唯一的。

• 根据以上特点，可以按顺序完成以下工作：
  1. 前序遍历的首个元素即为根节点

     root

     的值；
  2. 在中序遍历中搜索根节点

     root

     的索引 ，可将中序遍历划分为

     [ 左子树 | 根节点 | 右子树 ]

     。
  3. 根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为

     [ 根节点 | 左子树 | 右子树 ]

     。
• 自此可确定 三个节点的关系 ：1.树的根节点、2.左子树根节点、3.右子树根节点（即前序遍历中左（右）子树的首个元素）。

子树特点： 子树的前序和中序遍历仍符合以上特点，以题目示例的右子树为例：前序遍历：

[20 | 15 | 7]

，中序遍历

[ 15 | 20 | 7 ]

。

• 根据子树特点，我们可以通过同样的方法对左（右）子树进行划分，每轮可确认三个节点的关系 。此递推性质让我们联想到用 递归方法 处理。

递归解析：

• 递推参数： 前序遍历中根节点的索引

  pre_root

  、中序遍历左边界

  in_left

  、中序遍历右边界

  in_right

  。
• 终止条件： 当

  in_left > in_right

  ，子树中序遍历为空，说明已经越过叶子节点，此时返回 nullnullnull 。
• 递推工作：
  1. 建立根节点

     root

     ： 值为前序遍历中索引为

     pre_root

     的节点值。
  2. 搜索根节点

     root

     在中序遍历的索引

     i

     ： 为了提升搜索效率，本题解使用哈希表

     dic

     预存储中序遍历的值与索引的映射关系，每次搜索的时间复杂度为 O(1)O(1)O(1)。
  3. 构建根节点

     root

     的左子树和右子树： 通过调用

     recur()

     方法开启下一层递归。
     • 左子树： 根节点索引为

       pre_root + 1

       ，中序遍历的左右边界分别为

       in_left

       和

       i - 1

       。
     • 右子树： 根节点索引为

       i - in_left + pre_root + 1

       （即：根节点索引 + 左子树长度 + 1），中序遍历的左右边界分别为

       i + 1

       和

       in_right

       。
• 返回值： 返回

  root

  ，含义是当前递归层级建立的根节点

  root

  为上一递归层级的根节点的左或右子节点。

以下图解展示了题目示例树的建立全流程。

1 / 9

代码（Java）：

public class Solution {
	public static void main(String[] args) {
		int[] preorder = {3,9,20,15,7};
		int[] inorder = {9,3,15,20,7};
		TreeNode1 node = buildTree(preorder, inorder);//调试
		System.out.println();
	}
	
	static HashMap<Integer, Integer> dic = new HashMap<>();
    static int[] po;
    
    public static TreeNode1 buildTree(int[] preorder, int[] inorder) {
        po = preorder;
        for(int i = 0; i < inorder.length; i++)  //把前序遍历里面的元素确定在中序遍历里面的位置，便于确认左子树，右子树的长度
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    
    //in_left和in_left都是元素在中序遍历里面的位置，分表代表左子树边界和右子树边界，左子树边界到根节点，是构成左子树的元素 ，根节点到右子树边界，是构成右子树的元素
    public static TreeNode1 recur(int pre_root, int in_left, int in_right) {
        if(in_left > in_right) return null;
        TreeNode1 root = new TreeNode1(po[pre_root]);
        int i = dic.get(po[pre_root]);
        root.left = recur(pre_root + 1, in_left, i - 1); //这里又看做是新的一个二叉树，左子树的第一个节点作为根节点，这样左子树的左边界不会变，右边界就变成原来根节点的前面一个 节点了
        root.right = recur(pre_root + (i - in_left) + 1, i + 1, in_right);  //这里又看做是新的一个二叉树，右子树的第一个节点作为根节点，这样右子树的右边界不会变，左边界就变成原来根节点的后面一个 节点了
        return root;                   //i和in_left都是在中序遍历里面的位置，所以这两个要连在一起考虑，i是根节点的位置，in_left是左子树的边界，相减就是左子树节点的范围，
        							  //当前的根节点pre_root加上这个范围就是位置最靠后的左子树节点，加一就跳到右子树的第一个节点
    }
	
}
           

题目描述：

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

例如，给出

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

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

返回如下的二叉树：

限制：

0 <= 节点个数 <= 5000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

LeetCode的题解里面有这道题很详细的解析，但是仍然需要说明一下，起码是我看起来有点吃力的地方：

1、TreeNode本身在软件里面是一个接口（我用的是Eclipse 1.8），所以照着题目里面TreeNode的自定义类输入，是无法实例化的，必须要改个名字（我改成了TreeNode1）。

2、要注意里面位置的描述：in_left，in_right是在说中序遍历里面的左子树和右子树的边界，左子树边界in_left到根节点之间的节点是左子树包含的节点，根节点到右子树边界之间的节点是右子树包含的节点。

3、回溯里面的思想是将左子树和右子树的第一个节点作为根节点，这样后面跟着的又是一个二叉树，只是新的二叉树的左右边界有所改变。

题目分析：

前序遍历特点： 节点按照

[ 根节点 | 左子树 | 右子树 ]

排序，以题目示例为例：

[ 3 | 9 | 20 15 7 ]

中序遍历特点： 节点按照

[ 左子树 | 根节点 | 右子树 ]

排序，以题目示例为例：

[ 9 | 3 | 15 20 7 ]

根据题目描述

输入的前序遍历和中序遍历的结果中都不含重复的数字

，其表明树中每个节点值都是唯一的。

• 根据以上特点，可以按顺序完成以下工作：
  1. 前序遍历的首个元素即为根节点

     root

     的值；
  2. 在中序遍历中搜索根节点

     root

     的索引 ，可将中序遍历划分为

     [ 左子树 | 根节点 | 右子树 ]

     。
  3. 根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为

     [ 根节点 | 左子树 | 右子树 ]

     。
• 自此可确定 三个节点的关系 ：1.树的根节点、2.左子树根节点、3.右子树根节点（即前序遍历中左（右）子树的首个元素）。

子树特点： 子树的前序和中序遍历仍符合以上特点，以题目示例的右子树为例：前序遍历：

[20 | 15 | 7]

，中序遍历

[ 15 | 20 | 7 ]

。

• 根据子树特点，我们可以通过同样的方法对左（右）子树进行划分，每轮可确认三个节点的关系 。此递推性质让我们联想到用 递归方法 处理。

递归解析：

• 递推参数： 前序遍历中根节点的索引

  pre_root

  、中序遍历左边界

  in_left

  、中序遍历右边界

  in_right

  。
• 终止条件： 当

  in_left > in_right

  ，子树中序遍历为空，说明已经越过叶子节点，此时返回 nullnullnull 。
• 递推工作：
  1. 建立根节点

     root

     ： 值为前序遍历中索引为

     pre_root

     的节点值。
  2. 搜索根节点

     root

     在中序遍历的索引

     i

     ： 为了提升搜索效率，本题解使用哈希表

     dic

     预存储中序遍历的值与索引的映射关系，每次搜索的时间复杂度为 O(1)O(1)O(1)。
  3. 构建根节点

     root

     的左子树和右子树： 通过调用

     recur()

     方法开启下一层递归。
     • 左子树： 根节点索引为

       pre_root + 1

       ，中序遍历的左右边界分别为

       in_left

       和

       i - 1

       。
     • 右子树： 根节点索引为

       i - in_left + pre_root + 1

       （即：根节点索引 + 左子树长度 + 1），中序遍历的左右边界分别为

       i + 1

       和

       in_right

       。
• 返回值： 返回

  root

  ，含义是当前递归层级建立的根节点

  root

  为上一递归层级的根节点的左或右子节点。

以下图解展示了题目示例树的建立全流程。

1 / 9