大家好！我是曾续缘🧡
今天是《LeetCode 热题 100》系列
发车第 47 天
二叉树第 12 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给定两个整数数组 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 保证为二叉树的中序遍历序列
难度：💖💖

# 解题方法

对于任意一棵树，我们可以通过前序遍历和中序遍历的结果来构造出这棵树。

前序遍历的形式为[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]，

使用变量来表示就是[[(pre_l)], [(pre_l+1)...(pre_l+len_l)], [(pre_l+len_l+1)...(pre_r)] ]

中序遍历的形式为[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]。

使用变量来表示就是[ [(in_l)...(in_mid-1)], (in_mid), [(in_mid+1)...(in_r)] ]

其中

pre_l：当前子树在前序遍历结果中的左边界。
pre_r：当前子树在前序遍历结果中的右边界。
in_l：当前子树在中序遍历结果中的左边界。
in_r：当前子树在中序遍历结果中的右边界。

通过找到中序遍历的根节点，我们就可以确定左子树和右子树的节点数目。由于同一棵子树的前序遍历和中序遍历长度相同，我们可以将左右子树的范围映射到前序遍历结果中，重复这个过程递归构建左右子树，然后将它们连接到根节点的左右位置。

为了高效定位根节点，我们可以使用哈希表来记录中序遍历中每个节点值对应的位置。在构造二叉树之前，我们先扫描一遍中序遍历结果，生成这个哈希映射。之后在构造二叉树时，定位根节点只需要 O(1) 的时间。

Code

查看代码

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 {
    Map<Integer, Integer> mp;
    private TreeNode build(int[] preorder, int[] inorder, int pre_l, int pre_r, int in_l, int in_r){
        if(pre_l > pre_r){
            return null;
        }
        TreeNode root = new TreeNode(preorder[pre_l]);
    	// 找到中序遍历中当前子树的根节点位置
        int in_mid = mp.get(preorder[pre_l]);
    	// 计算左子树的长度
        int len_l = in_mid - in_l;
        root.left = build(preorder, inorder, pre_l + 1, pre_l + len_l, in_l, in_mid - 1);
        root.right = build(preorder, inorder, pre_l + len_l + 1, pre_r, in_mid + 1, in_r);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        mp = new HashMap<Integer, Integer>();
        for(int i = 0; i < n; i++){
            mp.put(inorder[i], i);
        }
        return build(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}

# 解题方法 ​

Code ​

# 解题方法

Code