好的，我们这次来详细讲解 LeetCode 第 105 题「从前序与中序遍历序列构造二叉树」。

1. 题目描述

题目链接：
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

题目要求：
给定一棵二叉树的前序遍历 preorder 和中序遍历 inorder，请构造出这棵二叉树，并返回其根节点。
假设树中没有重复的元素。

示例：

preorder = [3,9,20,15,7]
inorder  = [9,3,15,20,7]

返回的二叉树结构：

    3
   / \
  9  20
    /  \
   15   7

2. 理解前序与中序遍历的性质

在讲解解法前，必须清楚两种遍历的定义：

• 前序遍历（Preorder）：
  顺序：根 → 左子树 → 右子树
  特点：数组第一个元素一定是整棵树的根节点。

• 中序遍历（Inorder）：
  顺序：左子树 → 根 → 右子树
  特点：在数组里，根节点左边的所有元素属于左子树，右边的所有元素属于右子树。

3. 核心思路

1. 前序遍历数组 preorder 的第一个元素 preorder[preStart] 是当前子树的根节点值。

2. 在中序遍历数组 inorder 中找到这个根节点值的位置，记为 index（可以用哈希表提前存储值到索引的映射，加快查找）。

3. 中序遍历中：

   • 左子树区间：[inStart, index - 1]
   • 右子树区间：[index + 1, inEnd]

4. 根据左子树的长度，可以在前序遍历数组中划分出：

   • 左子树的前序区间：[preStart + 1, preStart + leftLength]
   • 右子树的前序区间：[preStart + leftLength + 1, preEnd]
   • 其中 leftLength = index - inStart。

5. 递归构建左子树和右子树，并连接到根节点上。

4. 详细步骤推导（用示例）

示例：

preorder = [3,9,20,15,7]
inorder  = [9,3,15,20,7]

步骤 1：
前序第一个是 3 → 根节点值是 3。
在中序数组中找到 3 的位置 index = 1（0-based）。

中序划分：

• 左子树中序区间：[9] (inorder[0:1])
• 右子树中序区间：[15,20,7] (inorder[2:4])

步骤 2：计算左子树节点个数 leftLength = index - inStart = 1 - 0 = 1。
前序划分：

• 左子树前序区间：[9] (preorder[1:2])
• 右子树前序区间：[20,15,7] (preorder[2:5])

步骤 3：递归构建左子树：
前序 [9]，中序 [9] → 根 9，左右子树为空。

步骤 4：递归构建右子树：
前序 [20,15,7]，中序 [15,20,7]
根是 20，在中序里 index=1（在右子树的中序区间内是 0-based index=1 对应全局 index=2+1=... 这里我们是在局部数组考虑，实际代码用索引值传递，不复制数组）。

我们继续：

• 中序中 20 的左边 [15] 是左子树，右边 [7] 是右子树。
• 前序中：根 20 之后第一个是 15（左子树根），然后是 7（右子树根）。

递归下去即可。

5. 递归函数设计

我们定义递归函数：

build(preorder, preStart, preEnd, inorder, inStart, inEnd, indexMap)

返回：构建的二叉树的根节点。

终止条件：如果 preStart > preEnd 或 inStart > inEnd，返回 null。

步骤：

1. 根值 rootVal = preorder[preStart]
2. 在 inorder 中找到 rootVal 的索引 rootIndex = indexMap[rootVal]
3. 左子树节点数 leftSize = rootIndex - inStart
4. 构建左子树：
   • 左子树前序区间：preStart+1 到 preStart+leftSize
   • 左子树中序区间：inStart 到 rootIndex-1
5. 构建右子树：
   • 右子树前序区间：preStart+leftSize+1 到 preEnd
   • 右子树中序区间：rootIndex+1 到 inEnd
6. 连接左右子树到根节点，返回根节点。

6. 代码实现（带注释）

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # 创建哈希表存储中序遍历的值到索引的映射，加速查找
        index_map = {val: idx for idx, val in enumerate(inorder)}
        
        def build(preStart, preEnd, inStart, inEnd):
            if preStart > preEnd or inStart > inEnd:
                return None
            
            # 前序遍历的第一个节点是根节点
            rootVal = preorder[preStart]
            root = TreeNode(rootVal)
            
            # 在中序遍历中找到根节点的位置
            rootIndexInorder = index_map[rootVal]
            
            # 计算左子树中的节点个数
            leftSize = rootIndexInorder - inStart
            
            # 递归构建左子树
            # 左子树在前序中的区间: [preStart+1, preStart+leftSize]
            # 左子树在中序中的区间: [inStart, rootIndexInorder-1]
            root.left = build(preStart + 1, preStart + leftSize, 
                              inStart, rootIndexInorder - 1)
            
            # 递归构建右子树
            # 右子树在前序中的区间: [preStart+leftSize+1, preEnd]
            # 右子树在中序中的区间: [rootIndexInorder+1, inEnd]
            root.right = build(preStart + leftSize + 1, preEnd, 
                               rootIndexInorder + 1, inEnd)
            
            return root
        
        n = len(preorder)
        return build(0, n - 1, 0, n - 1)

7. 复杂度分析

• 时间复杂度：O(n)
  每个节点只处理一次，哈希表查找 O(1)。
• 空间复杂度：O(n)
  哈希表 O(n)，递归栈深度平均 O(log n)，最坏 O(n)（树退化成链）。

8. 关键点总结

1. 前序确定根，中序划分左右子树。
2. 用哈希表存储中序索引，避免每次递归中线性查找。
3. 计算左子树节点个数来正确划分前序数组的左右子树区间。
4. 递归边界是区间起点大于终点时返回 null。

这样，我们就能高效且清晰地构造出二叉树。