重建二叉树 - Hexo

剑指 Offer 07. 重建二叉树

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

例如，给出

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

限制：0 <= 节点个数 <= 5000

解题思路：

首先，我们了解二叉树基本遍历知识：

前序遍历特点：节点按照【根节点|左子树|右子树】排序，以题目为例：【3|9|20 15 7】

中序遍历特点：节点按照【左子树|根节点|右子树】排序，以题目为例：【9|3|15 20 7】

题目中指定：输入的前序遍历和中序遍历的结果都不含重复的数字，表明树中节点唯一

根据以上特点，按照顺序

1. 前序遍历的首个节点即是根节点`root`的值
  2. 在中序遍历中搜索根节点`root`的索引，可将中序遍历划分为【左子树|根节点|右子树】
  3. 根据中序遍历中的左（右）子树的节点数量，可以将前序遍历划分为【根节点|左子树|右子树】

自此可以确定三个节点的关系：

1. 树的根节点 
 2. 左子树根节点 
 3. 右子树根节点（即前序遍历中左（右）子树的首个元素）

那么我们可以使用递归的方法进行处理：每轮确定三个节点的关系

递归：

递归参数：前序遍历中根节点索引为pre_root, 中序遍历左边界in_left, 中序遍历右边界 in_right
终止条件：当in_left>in_right ，子树中序遍历为空，说明已经越过了叶子节点，返回NULL
递推工作
1. 建立根节点root：值为前序遍历中索引为pre_root的节点值
2. 搜索根节点root在中序遍历中的索引，确定左右子树：这里我们使用哈希表dic预存储中序遍历的值与索引的对应关系
3. 构建根节点root的左子树和右子树：通过调用递归函数 recur() 开始下一层递归
  - 左子树：根节点索引为pre_root+1,中序遍历的左右边界分别为in_left 和 i-1
  - 右子树：根节点索引为i - in_left + pre_root + 1 （即：根节点索引+左子树长度+1），中序遍历的左右边界分别为 i+1 和 in_right

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

代码展示：

class Solution {
    HashMap<Integer, Integer> dic = new HashMap<>();
    int[] po;
    public TreeNode 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);
    }
    TreeNode recur(int pre_root, int in_left, int in_right) {
        if(in_left > in_right) return null;
        TreeNode root = new TreeNode(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;
    }
}

作者：jyd
链接：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/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。