105. 从前序与中序遍历序列构造二叉树

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

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

DFS，哈希表ValToIndex

哈希表存储二叉树中的值对应的索引，根据这个哈希表确定构造左右子树时需要的数据。

想用递归的方式来构建一棵树，我们需要知道root，root.left和root.right。

注意到前序遍历的格式如下：

[root, [root.left], [root.right]]

中序遍历的格式如下：

[[root.left], root, [root.right]]

从前序遍历我们可以得知root，但是不知道root.left和root.right的分界线，从而不能确定root.left和root.right。

从中序遍历我们可以得知的信息更少，两个分界线我们都不知道。但是我们可以利用一个HashMap得知root在中序遍历中的索引，这样我们就知道了root.left和root.right。 具体来说是这样：

我们一开始使用的是 preorder 中 [0, preorder.length - 1] 的元素和 inorder 中 [0, inorder.length-1] 的元素， 然后我们确定了root，并利用HashMap确定了root在inorder中的索引 i。确定了 i 后我们还要确定preorder中root.left的大小 leftSize。

有了 i 和 size，我们在确定子问题root.left时需要的数据就是preorder中的roo.left和inorder中的root.left， 即 preorder 中的 [1, leftSize] 和 inorder 中的 [0, i-1] 中的元素。 我们在确定子问题root.right时需要的数据就是preorder中的roo.right和inorder中的root.right， 即 preorder 中的 [leftSize+1, preorder.length-1] 和 inorder 中的 [i+1, inorder.length-1] 中的元素。

class Solution {
    // 定义存储中序遍历中值到索引的映射
    Map<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 利用中序遍历初始化valToIndex
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        
        // 执行递归
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    TreeNode build(int[] preorder, int preStart, int preEnd,
                   int[] inorder, int inStart, int inEnd) {
        // 终止条件
        if (preStart > preEnd) {
            return null;
        }

        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preorder[preStart];
        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);
        
        // index 是 rootVal 在中序遍历数组中的索引，根据这个索引可以确定左右子树的大小。重点。
        int index = valToIndex.get(rootVal);
        int leftSize = index - inStart;
        // 然后递归构造左右子树
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                inorder, inStart, index - 1);
        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                inorder, index + 1, inEnd);
        
        return root;
    }
}

• 时间复杂度: $O(n)$ ，其中 $n$ 是树中的节点个数。
• 空间复杂度: $O(n)$ ，除去返回的答案需要的 $O(n)$ 空间之外，我们还需要使用 $O(n)$ 的空间存储哈希映射，以及 $O(h)$ (其中 $h$ 是树的高度) 的空间表示递归时栈空间。这里 $h<n$ ，所以总空间复杂度为 $O(n)$​ 。