构造二叉树

## 根据前序遍历和中序遍历构造二叉树

### 题目

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

例如，给出

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

返回如下的二叉树：

![](https://notebook.ricear.com/media/202104/2021-04-28_210531.png)

**限制：**

```txt
0 <= 节点个数 <= 5000
```

### 问题分析

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

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

根据以上性质，可得出以下结论：

1. **前序遍历**的**首元素**为树的**根节点 `node` 的值**。
2. 在**中序遍历**中搜索**根节点 `node` 的索引**，可将**中序遍历**划分为 `[左子树 | 根节点 | 右子树]`。
3. 根据**中序遍历**中的**左/右子树的节点数量**，可将**前序遍历**划分为 `[根节点 | 左子树 | 右子树]`。

通过以上三步，可确定三个节点：**树的根节点**、**左子树根节点**、**右子树根节点**。对于树的左、右子树，仍可使用以上步骤划分子树的左右子树。

以上子树的递归性质是**分治算法**的体现，考虑通过递归对所有子树进行划分。

**分治算法解析**：

1. **递推参数：** 
   1. **根节点**在**前序遍历的索引** `root`。
   2. **子树**在**中序遍历的左边界**`left`。
   3. **子树**在**中序遍历的右边界**`right`。
2. **终止条件：** 
   1. 当 `left > right` 时，代表已经越过叶节点，此时返回 `null`。
3. **递推工作：**
   1. **建立根节点**`node`：节点值为 `preOrder[root]`。
   2. **划分左右子树：** 查找**根节点**在**中序遍历 `inOrder`** 中的索引 `i`。
   3. **构建左右子树：** 开启左右子树递归。

| **根节点索引**（前序遍历）                | **中序遍历左边界**（中序遍历） | **中序遍历右边界**（中序遍历） |
| :---------------------------------------- | ------------------------------ | ------------------------------ |
| root + 1                                  | left                           | map.get(preOrder[root]) - 1    |
| root + map.get(preOrder[root]) - left + 1 | map.get(preOrder[root]) + 1    | right                          |

4. **返回值：** 回溯返回 `node`，作为上一层递归中根节点的左/右子节点。

> :warning: 本方法只适用于**无重复节点值**的二叉树。

### 参考代码

```java
HashMap<Integer, Integer> inValueAndIndexMap = new HashMap<>(); //  哈希表，其中 key 为二叉树节点的值，value 为二叉树节点的值在后序遍历中的索引

/**
 * 剑指 Offer 07. 重建二叉树
 *
 * @param preorder 前序遍历数组
 * @param inorder  中序遍历数组
 * @return 二叉树
 */
public TreeNode buildTree(int[] preorder, int[] inorder) {
    this.preOrder = preorder;
    int m = inorder.length;
    for (int i = 0; i < m; i++) {
        inValueAndIndexMap.put(inorder[i], i);
    }
    return recur(preOrder, 0, 0, m - 1);
}

/**
 * 递归构建二叉树
 *
 * @param root  根节点在前序遍历中的索引
 * @param left  子树在中序遍历的左边界
 * @param right 子树在中序遍历的右边界
 * @return 二叉树
 */
private TreeNode recur(int[] preorder, int root, int left, int right) {
    if (left > right) {return null;}    //  已经越过叶节点，返回 null

TreeNode node = new TreeNode(preOrder[root]);
    node.left = recur(preOrder, root + 1, left, inValueAndIndexMap.get(preOrder[root]) - 1);
    node.right = recur(preOrder, root + inValueAndIndexMap.get(preOrder[root]) - left + 1, inValueAndIndexMap.get(preOrder[root]) + 1, right);

return node;
}
```

## 参考文献

1. [剑指 Offer 07. 重建二叉树](https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof)。
2. [面试题 07. 重建二叉树（递归法，清晰图解）](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)。