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. 前序遍历的第一个元素是当前子树的根节点。
2. 在中序遍历中找到根节点的位置，其左侧为左子树的中序序列，右侧为右子树的中序序列。
3. 根据中序序列的长度，在前序序列中划分出左子树和右子树的前序序列。
4. 递归构造左子树和右子树，并将其分别连接到根节点的左、右指针。

算法步骤

1. 终止条件：前序或中序序列为空时，返回 null。
2. 确定根节点：前序序列的第一个元素为根节点的值。
3. 划分左右子树：在中序序列中找到根节点的索引 i，划分出左子树（inorder[0..i-1]）和右子树（inorder[i+1..end]）。
4. 递归构造子树：
   • 左子树的前序序列为 preorder[1..i]，中序序列为 inorder[0..i-1]。
   • 右子树的前序序列为 preorder[i+1..end]，中序序列为 inorder[i+1..end]。
5. 返回根节点：将左右子树连接到根节点后，返回根节点。

---

代码实现

递归法（Java）

import java.util.Arrays;

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 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[0]) {
                int[] preorderLeft = Arrays.copyOfRange(preorder, 1, i + 1);
                int[] preorderRight = Arrays.copyOfRange(preorder, i + 1, preorder.length);
                int[] inorderLeft = Arrays.copyOfRange(inorder, 0, i);
                int[] inorderRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);
                root.left = buildTree(preorderLeft, inorderLeft);
                root.right = buildTree(preorderRight, inorderRight);
                break;
            }
        }
        return root;
    }
}

优化递归法（哈希表加速查找）

import java.util.*;

class Solution {
    Map<Integer, Integer> inorderMap = new HashMap<>();
    int[] preorder;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(0, 0, inorder.length - 1);
    }
    
    private TreeNode build(int preRoot, int inLeft, int inRight) {
        if (inLeft > inRight) return null;
        TreeNode root = new TreeNode(preorder[preRoot]);
        int inRoot = inorderMap.get(preorder[preRoot]);
        root.left = build(preRoot + 1, inLeft, inRoot - 1);
        root.right = build(preRoot + (inRoot - inLeft) + 1, inRoot + 1, inRight);
        return root;
    }
}

---

复杂度分析

基础递归法

• 时间复杂度：O(n²)，其中 n 是节点数。每次递归需要遍历中序序列找到根节点，最坏情况下为 O(n)，递归深度为 O(n)。
• 空间复杂度：O(n)，递归栈深度为 O(n)，且需要存储子数组。

优化递归法（哈希表）

• 时间复杂度：O(n)，哈希表查找根节点的时间为 O(1)，每个节点仅被访问一次。
• 空间复杂度：O(n)，哈希表存储 n 个元素，递归栈深度为 O(n)。

---

总结

1. 基础递归法通过数组拷贝划分左右子树，实现简单但效率较低。
2. 优化递归法使用哈希表存储中序序列的索引，将查找根节点的时间从 O(n) 降为 O(1)，显著提升效率。
3. 该方法的核心是利用前序和中序遍历的特性，递归划分左右子树，适用于任意二叉树的构造。

---