105. 从前序与中序遍历序列构造二叉树：分治算法从底至上地构建二叉树，深刻理解三种DFS前、中、后序遍历的顺序和特征.md

题目简述：

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

提示: preorder 和 inorder 均 无重复 元素

题目链接：105. 从前序与中序遍历序列构造二叉树

导言

我们先来分析下先序遍历和中序遍历的特点。

我们要构建（一棵各节点不保存父节点）树，最直观的想法是从根节点开始自上而下地构建。恰好，先序遍历的顺序是 根节点 -> 左子树 -> 右子树，因此先序遍历的第一个元素一定是根节点。

那么，对于剩下的节点我们该怎么办呢？中序遍历的顺序是 左子树 -> 根节点 -> 右子树，我们先考虑深度为3的满二叉树：

所有的遍历都从整棵树的根开始，并且只在访问子树根节点时进行操作。

具体该怎么做呢？我们举个例子，假设给出的前序遍历是 [3, 9, 20, 15, 7]、中序遍历是 [9, 3, 15, 20, 7]，

首先从整棵树的根节点、即值为 3 的节点开始分析，可以进行如下分割：

• 根据前序遍历 [| 3 | 9, 20, 15, 7] 可知， 剩余节点均属于根节点的子树。
• 根据中序遍历 [9 | 3 |15, 20, 7] 可知，[9] 必然是根节点的左子树，[15, 20, 7] 必然是值为 20 节的右子树。
• 无法确定其右子树的结构，需要进一步分析。

然后我们分析值为 9 的节点，由于 [9] 是根节点的左子树，因此值为 9 的节点是叶子节点，独自构成一棵子树。

接下来我们再分析值为 20 的节点，可以进行如下分割：

• 根据前序遍历 [3, 9 | 20 | 15, 7] 可知，[3, 9] 不可能是其子树，子树为 [15, 7]、[15]、[] 中的一个。
• 根据中序遍历 [9, 3, 15 | 20 | 7] 可知，其左子树是 [9, 3, 15]、[3, 15]、[15]、[] 中的一个，右子树是 [7]、[] 中的一个。
• 综上，值为 20 的节点左子节点只可能是 15，右子节点只可能是 7。

可是该如何处理更一般的的树呢？又如何通过程序实现呢？

分治算法（重点）

在刚才的例子中，蕴含着分治算法的应用。

接下来我们以一棵树为例，注意是一棵树而不是一个节点，这棵树可以是最大的树，也可以是任意一个具有根节点的子树。再次强调，我们分析的是一棵树，而不是一个节点，这里是个坑点，如果只关注某个节点在前序序列和中序序列中的位置是不可能递归找出解的，我们要关注的是整棵树以及这棵树的前序序列与中序序列——这棵树的前序序列与中序序列很可能只是最大的树的前序序列与中序序列的其中一段——这部分将会成为我们递归分治算法的输入。

题干给我们的输入是最大的数的前序序列与中序序列，这其中蕴含了树的完整结构，要递归实现分治算法，我们应当分别找出根节点的左右子树各自的两种序列，并分别将两棵子树的前序序列与中序序列作为输入并将两棵子树分别视为分治算法下的独立的树（而不再视为谁的子树），这样我们就将原问题拆解为了子问题。

递归的结束条件为输入的序列为空，意味着调用递归的节点该子树/子节点不存在。

首先我们根据前序序列 根节点 -> 左子树 -> 右子树 的特性可以知道其第一个元素就是根节点，于是先获取到根节点。

我们再来看看中序序列 左子树 -> 根节点 -> 右子树 的特性，这很好，利用值不重复的前提，我们只需要做一个哈希映射就可以在 $O(1)$ 的时间内找到根节点，那么根节点左侧的就是左子树的中序排列，根节点的右侧就是右子树的中序排列。

现在我们找到左右子树的中序序列了，接下来需要的是再找出左右子树的前序排列。回到输入的前序序列，问题的关键是找出输入序列中左子树与右子树的分界点，这样我们才可以分割开左半边的左子树前序序列与右半边的右子树前序序列。现在问题变为了，如何找到输入前序序列中左子树与右子树的分割？这很好办，因为虽然前序序列与中序序列中节点的排列、顺序不一样，但每个子树包含的节点个数是不变的，因此我们只需要读取左子树中序序列的长度 k，那么再回到前序序列，根节点右边的 k 个节点就是左子树的前序序列，剩余的节点为右子树的前序序列。

接下来再分别对左子树（的前序序列与中序序列）与右子树（的前序序列与中序序列）递归就可以了，递归返回子树的根节点，我们将（递归调用方的）根节点左子节点赋值左子树的递归返回值、右子节点赋值右子树的递归返回值。

现在，我们只需要初始化一下递归就大功告成了。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */


class Solution {
    int[] preorder;
    int[] inorder;
    HashMap<Integer, Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i);
        return divideAndConque(0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode divideAndConque(int pre1, int pre2, int in1, int in2) {
        int rootVal = preorder[pre1];
        TreeNode root = new TreeNode(rootVal);
        int rootInorderIndex = map.get(rootVal);
        int leftSubtreeLength = rootInorderIndex - in1;
        
        root.left = leftSubtreeLength > 0 ? divideAndConque(pre1 + 1, pre1 + leftSubtreeLength, in1, rootInorderIndex - 1) : null;
        root.right = pre2 - pre1 - leftSubtreeLength > 0 ? divideAndConque(pre1 + leftSubtreeLength + 1, pre2, rootInorderIndex + 1, in2) : null;
        
        return root;
    }
}

这里我没有显式地写出递归条件，递归终止条件蕴含在三元运算符中赋 null 的情况中。