【算法题解】47. 从前序与中序遍历序列构造二叉树

❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

❞

题目

给定两个整数数组 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]

提示:

,
和均 「无重复」 元素
均出现在
「保证」 为二叉树的前序遍历序列
「保证」 为二叉树的中序遍历序列

递归解法

首先可以知道前序遍历数组中的第一个元素（）为根结点。

以示例一为例：其中 , ，
那么。

然后将中序遍历数组以根节点为界，一分为二就可以分别得到左右子树包含有哪些节点。如示例一中的，那么根节点前面的都是其左子树中的节点，后面的都是其右子树的节点。即左子树的中序遍历数组应该为，右子树的中序遍历数组为。

知道左右子树的中序遍历后，还需要知道对应的前序遍历才能过还原左右子树（知道前序遍历后才能知道哪个是子树的根结点）。

我们知道，不管是前序还是中序，其中的节点数肯定是固定且相等的。假设左子树的中序有 m 个节点，那么其前序肯定也是 m 个节点。所以从前序遍历数组中的根节点开始，依次取 m 个节点就是左子树的前序遍历，剩下的自然而然就是右子树的前序遍历了。

还是以示例一为例，左子树的前序遍历为，右子树的前序遍历为。

到目前为止，知道了根节点 root，只要求得 root 的左右子树便可得到整颗二叉树。

然后我们又知道了左右子树的前序和中序，用来还原左右子树。这和题目要求的还原二叉树一模一样，也就是题目的一个子问题，同样这也就是递归函数了，一层一层的往下求，然后再一层一层的往上合并。

为了解题方便，每次递归时都不去改变 preorder 和 inorder 这两个数组，而是使用两个下标变量 pl 和 pr 去规定前序遍历数组 preorder 的取值范围，使用 il 和 ir 规定中序遍历数组 inorder 的取值范围。递归函数定义如下：

 private TreeNode build(int[] preorder, int pl, int pr, int[] inorder, int il, int ir){
     // TODO
 }

边界条件：递归势必要有边界，不然就会无限递归下去，永远也结束不了了。对于这道题而言，只要也就是前序遍历不空的时候就一定有解，所以当的时候就是边界条件了，也就是前序遍历为空的时候直接返回 null 即可。

Java 代码实现

/**
 * 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 {
    private Map<Integer, Integer> inorderIndexMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++){
            inorderIndexMap.put(inorder[i], i);
        }
        TreeNode root = build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        return root;
    }

    private TreeNode build(int[] preorder, int pl, int pr, int[] inorder, int il, int ir){
        // 边界条件
        if(pl > pr){
            return null;
        }
        int rootVal = preorder[pl];
        TreeNode root = new TreeNode(rootVal);

        // 计算根节点在中序遍历中的位置
        int rootInorderIndex = inorderIndexMap.get(rootVal);

        // 左子树的中序遍历 inorder 位置从 il -> rootInorderIndex - 1;

        // 左子树节点个数
        int m = rootInorderIndex - il;

        // 右子树的中序遍历 inorder 位置从 rootInorderIndex + 1 -> ir;

        // 左子树的前序遍历 preorder 位置从 pl + 1 -> pl + m 

        // 右子树的前序遍历 preorder 位置从 pl + m + 1  -> pr

        // 递归
        root.left = build(preorder, pl + 1, pl + m, inorder, il, rootInorderIndex - 1);
        root.right = build(preorder, pl + m + 1, pr, inorder, rootInorderIndex + 1, ir);

        return root;
        
    }
}

因为每次递归都需要在中序遍历数组 inorder 中找到本次的根节点位置，也就是每次都遍历一遍 inorder，虽然不是全部，是根据 il 和 ir 规定了范围的，但还是有重复遍历多次的位置。

所以我们可以提前将这些值和对应中序遍历数组的位置缓存到一个哈希表 inorderIndexMap 中，这样只需遍历一次，需要的时候直接查就可以了。

Go 代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {

    inorderIndexMap := make(map[int]int, 0)
    for i := 0; i < len(inorder); i++ {
        inorderIndexMap[inorder[i]] = i
    }

    var build func(pl int, pr int, il int, ir int) *TreeNode

    build = func(pl int, pr int, il int, ir int) *TreeNode {
        if pl > pr {
            return nil
        }
        rootVal := preorder[pl]
        rootInorderIndex := inorderIndexMap[rootVal]

        root := &TreeNode{rootVal, nil, nil}

        m := rootInorderIndex - il


        root.Left = build(pl + 1, pl + m, il, rootInorderIndex - 1)
        root.Right = build(pl + m + 1, pr, rootInorderIndex + 1, ir)

        return root
    }

    return build(0, len(preorder) - 1, 0, len(inorder) - 1)

}