题解 | #动图来解# 剑指 Offer 07. 重建二叉树（分治算法，清晰图解）

前提知识点

前序遍历性质：节点按照 [ 根节点 | 左子树 | 右子树 ] 进行排序。

中序遍历性质：节点按照 [ 左子树 | 根节点 | 右子树 ] 进行排序。

看题举的例子：

前序遍历划分成 [ 3 | 9 | 20 15 7 ]
中序遍历划分成 [ 9 | 3 | 15 20 7 ]

我的思路

根据上面的性质，可以得出下面的推论哈

前序遍历的首元素是树的根节点 node 的值。
在中序遍历中去搜索根节点 node 的索引，可把中序遍历划分成 [ 左子树 | 根节点 | 右子树 ]
根据中序遍历的左（右）子树的节点数量，可把前序遍历划分成 [ 根节点 | 左子树 | 右子树 ]

通过上面三步骤，可以确定三个节点：1.树的根节点、2.左边子树的根节点、3.右边子树的根节点

根据「分治算法」的套路，对于树的左、右子树，仍然可以复用以上方法来划分子树的左右子树呀

分治算法解析如下

递推参数：根节点在前序遍历的索引为 root 、子树在中序遍历的左边界为 left 、子树在中序遍历的右边界为 right；
终止条件：当 left > right的时候，就代表已经越过叶子节点，此时就返回 null；
递推工作：

1. 建立根节点 node ：节点值是 preorder[root] ；

2. 划分左右子树：查找根节点在中序遍历 inorder 中的索引值为 i ；

我们为了提升效率，用哈希表 dic 去存中序遍历的值与索引的映射，这样查找操作的时间复杂度是 O(1)

3. 构建左右子树：开始左右子树开始递归；

alt

敲黑板：i-left+root+1的含义是根节点索引 + 左边子树的长度 + 1

返回值：回溯返回 node ，作为上一层递归中根节点的左 / 右子节点；

复杂度分析下

时间复杂度是 O(N)：其中 N 是树的节点数量。初始化 HashMap 需要遍历 inorder ，占用了 O(N) 。递归共建立 N 个节点，每层递归中的节点建立、搜索操作共占用 O(1)，所以复杂度用了 O(N) 时间。
空间复杂度也是 O(N)：首先 HashMap 使用 O(N) 额外空间；最差情况下（也就是输入二叉树为链表的时候），递归深度达到 N，那么占用 O(N) 的栈帧空间；所以总共使用 O(N) 空间啦。

敲黑板：我说的方法只用于 “无重复节点值” 的二叉树。

完整代码如下

//Java的版本
class Solution {
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int root, int left, int right) {
        if(left > right) return null;                          // 递归终止
        TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
        int i = dic.get(preorder[root]);                       // 划分根节点、左子树、右子树
        node.left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                           // 回溯返回根节点
    }
}

//python的版本
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def recur(root, left, right):
            if left > right: return                               # 递归终止
            node = TreeNode(preorder[root])                       # 建立根节点
            i = dic[preorder[root]]                               # 划分根节点、左子树、右子树
            node.left = recur(root + 1, left, i - 1)              # 开启左子树递归
            node.right = recur(i - left + root + 1, i + 1, right) # 开启右子树递归
            return node                                           # 回溯返回根节点

        dic, preorder = {}, preorder
        for i in range(len(inorder)):
            dic[inorder[i]] = i
        return recur(0, 0, len(inorder) - 1)