leetcode105.从中序与前序遍历序列构造二叉树：前序定根与中序分治的递归重建术

一、题目深度解析与核心挑战

在二叉树的重建问题中，"从中序与前序遍历序列构造二叉树"是一道考察递归分治思想的经典题目。题目要求我们根据一棵二叉树的前序遍历序列和中序遍历序列，重建出该二叉树的原始结构。这道题的核心难点在于如何利用两种遍历序列的特性，高效定位子树的根节点，并通过递归分治策略构建完整的树结构。

遍历序列特性回顾：

• 前序遍历（Preorder）：根-左-右，第一个元素是当前子树的根节点
• 中序遍历（Inorder）：左-根-右，根节点将序列分为左子树和右子树两部分

示例输入输出：

输入：

前序 preorder = [3,9,20,15,7]
中序 inorder = [9,3,15,20,7]

输出：

    3/ \9  20/  \15   7

重建的核心逻辑在于：每次通过前序的第一个元素确定根节点，再通过中序中根节点的位置分割出左右子树的范围，递归构建子树。

二、递归解法的核心实现与数据结构设计

完整递归代码实现

/*** 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> map; // 存储中序值到索引的映射public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i); // 预处理中序索引，O(n)时间}return findTree(preorder, 0, preorder.length, inorder, 0, inorder.length);}public TreeNode findTree(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {if (preBegin >= preEnd || inBegin >= inEnd) {return null; // 子数组为空，返回null}// 前序第一个元素是当前子树的根节点int rootVal = preorder[preBegin]; int rootIndex = map.get(rootVal); // 中序中根节点的索引TreeNode root = new TreeNode(rootVal); // 创建根节点// 计算左子树长度：中序中根节点左边的元素个数int lenLeft = rootIndex - inBegin; // 递归构建左子树：前序[preBegin+1, preBegin+lenLeft+1)，中序[inBegin, rootIndex)root.left = findTree(preorder, preBegin + 1, preBegin + lenLeft + 1, inorder, inBegin, rootIndex);// 递归构建右子树：前序[preBegin+lenLeft+1, preEnd)，中序[rootIndex+1, inEnd)root.right = findTree(preorder, preBegin + lenLeft + 1, preEnd, inorder, rootIndex + 1, inEnd);return root;}
}

核心数据结构设计：

1. HashMap映射表：

   • 作用：快速查找中序遍历中值对应的索引（O(1)时间复杂度）
   • 预处理：遍历中序数组，将每个值与其索引存入map
   • 关键价值：避免每次查找根节点索引时遍历中序数组，将时间复杂度从O(n²)优化到O(n log n)

2. 递归函数参数：

   • preBegin/preEnd：前序数组当前处理的子数组范围（左闭右开）
   • inBegin/inEnd：中序数组当前处理的子数组范围（左闭右开）
   • 意义：通过索引范围精确划分当前子树的左右子树区域，避免数据拷贝

三、核心问题解析：索引定位与递归分治过程

1. 根节点定位的核心逻辑

前序遍历的根节点特性

int rootVal = preorder[preBegin]; // 前序第一个元素是根节点
int rootIndex = map.get(rootVal); // 中序中根节点的位置

• 前序特性：前序遍历的第一个元素必定是当前子树的根节点（先访问根节点，再访问左右子树）
• 中序分割：根节点在中序中的位置将序列分为左子树（左边元素）和右子树（右边元素）

示例说明：

• 前序数组[3,9,20,15,7]的第一个元素是3，确定根节点为3
• 中序数组[9,3,15,20,7]中3的索引是1，左边是左子树[9]，右边是右子树[15,20,7]

2. 左右子树的索引划分

左子树范围确定

int lenLeft = rootIndex - inBegin; // 左子树元素个数
// 前序左子树范围：preBegin+1 到 preBegin+lenLeft+1
root.left = findTree(preorder, preBegin + 1, preBegin + lenLeft + 1, inorder, inBegin, rootIndex);

• 中序左子树：从inBegin到rootIndex（左闭右开，包含根节点左边的所有元素）
• 前序左子树：前序中左子树的元素个数与中序左子树相同，起始索引为preBegin+1（跳过根节点），结束索引为preBegin+lenLeft+1

右子树范围确定

// 中序右子树：从rootIndex+1到inEnd
// 前序右子树：左子树之后到preEnd（左子树结束索引为preBegin+lenLeft+1）
root.right = findTree(preorder, preBegin + lenLeft + 1, preEnd, inorder, rootIndex + 1, inEnd);

• 关键公式：前序中右子树的起始索引 = 左子树结束索引（preBegin+lenLeft+1）
• 逻辑推导：前序中根节点后，先排列左子树所有元素，再排列右子树所有元素，因此右子树的起始位置是左子树结束之后

3. 递归终止条件

if (preBegin >= preEnd || inBegin >= inEnd) {return null;
}

• 触发场景：当子数组长度为0（preBegin == preEnd或inBegin == inEnd）
• 逻辑意义：表示当前子树不存在，返回null作为叶子节点的子节点，确保递归正确终止

四、递归分治流程模拟：以示例输入为例

示例输入：

• 前序：[3,9,20,15,7]（索引0-4）
• 中序：[9,3,15,20,7]（索引0-4）

详细递归过程：

1. 第一次调用（构建整棵树）：

   • preBegin=0, preEnd=5；inBegin=0, inEnd=5
   • 根节点：preorder[0]=3，中序索引1
   • 左子树长度：1-0=1（元素9）
   • 右子树长度：5-1-1=3（元素15,20,7）

2. 构建左子树：

   • 前序范围[1,2]（元素9），中序范围[0,1]（元素9）
   • 根节点：preorder[1]=9，中序索引0
   • 左右子树长度均为0，递归终止，左子树为叶子节点9

3. 构建右子树：

   • 前序范围[2,5]（元素20,15,7），中序范围[2,5]（元素15,20,7）
   • 根节点：preorder[2]=20，中序索引3
   • 左子树长度：3-2=1（元素15），右子树长度：5-3-1=1（元素7）

4. 右子树的左子树（15）：

   • 前序范围[3,4]（元素15），中序范围[2,3]（元素15）
   • 根节点：preorder[3]=15，中序索引2，左右子树为空，构建叶子节点15

5. 右子树的右子树（7）：

   • 前序范围[4,5]（元素7），中序范围[4,5]（元素7）
   • 根节点：preorder[4]=7，中序索引4，左右子树为空，构建叶子节点7

最终构建的树结构：

    3/ \9  20/  \15   7

五、算法复杂度分析

1. 时间复杂度

• O(n)：每个节点仅被创建一次，HashMap预处理O(n)，每次递归分割子数组O(1)
• 分治策略下，每个层级的总操作数为O(n)，总共有O(log n)层（平衡树），最坏O(n)层（链表树），总体仍为O(n)

2. 空间复杂度

• O(n)：HashMap存储n个元素，递归栈深度O(n)（最坏情况树退化为链表）

3. 核心优化点

• HashMap索引预处理：将中序索引查找从O(n)优化到O(1)，避免双重循环
• 分治策略：通过索引范围划分，每次递归将问题规模减半，符合分治思想
• 无数据拷贝：通过索引范围传递，避免复制子数组，节省空间

六、核心技术点总结：前序中序重建的三大关键步骤

1. 根节点的唯一性定位

• 前序特性：第一个元素是根节点，确保每次递归有且仅有一个根节点
• 中序分割：根节点在中序中的位置将序列分为左右子树，保证子问题独立性
• 时间优化：HashMap实现O(1)时间的根节点定位

2. 子树范围的数学推导

• 左子树长度：rootIndex - inBegin（中序左边元素个数）
• 前序左子树范围：起始索引=preBegin+1，结束索引=preBegin+lenLeft+1
  • 解释：preBegin是根节点索引，+1跳过根节点，+lenLeft是左子树元素个数，+1是因为左闭右开
• 前序右子树范围：起始索引=左子树结束索引，结束索引=preEnd

3. 递归终止的边界处理

• 空数组判断：当子数组长度为0时返回null，作为递归终止条件
• 正确性保证：每个子树的左右边界通过索引严格控制，避免越界访问
• 逻辑闭环：递归终止时返回null，确保叶子节点的子节点正确设置

七、常见误区与边界情况处理

1. 空树处理

• 输入为空数组时，preBegin >= preEnd自动触发，返回null，无需额外处理

2. 单节点树

• 前序和中序均只有一个元素，直接创建节点，递归终止条件正确处理
• 示例：preorder=[1], inorder=[1]，直接返回节点1

3. 完全左/右子树

• 例如前序[1,2,3]，中序[1,2,3]，根节点是1，左子树为空，右子树递归构建2和3
• 关键：正确计算lenLeft=0，前序右子树范围为preBegin+0+1=1到preEnd=3，即元素2和3

八、总结：递归分治在树重建中的设计哲学

本算法通过"前序定根-中序分治-递归构建"的三步策略，完美解决了从中序与前序序列重建二叉树的问题。其核心设计哲学包括：

1. 特性利用：

   • 前序遍历的根节点特性（第一个元素）
   • 中序遍历的左右子树划分特性

2. 索引魔法：

   • 通过HashMap实现中序值到索引的快速查找
   • 利用数学推导确定前序中左右子树的索引范围，实现O(1)时间的子数组划分

3. 递归分治：

   • 将原问题分解为左右子树的重建子问题
   • 通过索引范围传递，避免数据拷贝，实现线性时间复杂度

这种解法不仅高效，而且逻辑清晰，充分体现了递归分治在树结构问题中的优势。理解索引定位的数学推导和递归边界的处理，是掌握此类问题的关键。在实际应用中，这种分治思想还可迁移到后序与中序重建、不同遍历序列的树重建等问题中，具有很强的通用性。

通过前序和中序重建二叉树的核心，在于利用两种遍历序列的特性，将树的重建问题转化为子树的递归重建问题，而索引的正确划分则是实现这一转化的关键桥梁。