从前序与中序遍历序列构造二叉树

题目描述
给定一棵二叉树的前序遍历 preorder 和中序遍历 inorder，请构造二叉树并返回其根节点。假设二叉树中节点值互不相同。

解题过程

步骤 1：理解前序与中序遍历的性质

• 前序遍历：根节点 → 左子树 → 右子树（顺序：根、左、右）。
• 中序遍历：左子树 → 根节点 → 右子树（顺序：左、根、右）。

关键观察：

1. 前序遍历的第一个节点一定是整棵树的根节点。
2. 在中序遍历中找到根节点，其左侧是左子树的中序遍历，右侧是右子树的中序遍历。
3. 根据左子树的节点数量，可以在前序遍历中划分出左子树和右子树的前序遍历。

步骤 2：递归构造的思路

1. 从前序遍历获取根节点的值。
2. 在中序遍历中找到根节点的位置 rootIndex。
3. 计算左子树的节点数量：leftSize = rootIndex - inorderStart。
4. 递归构造左子树：
   • 左子树的前序遍历区间：从根节点后一个节点开始，长度为 leftSize。
   • 左子树的中序遍历区间：中序遍历中根节点左侧的部分。
5. 递归构造右子树：
   • 右子树的前序遍历区间：左子树区间之后的所有节点。
   • 右子树的中序遍历区间：中序遍历中根节点右侧的部分。

步骤 3：具体例子演示

例：

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

1. 根节点是 3（前序第一个）。
2. 在中序中找到 3，左侧 [9] 是左子树中序，右侧 [15,20,7] 是右子树中序。
3. 左子树节点数 = 1，因此左子树前序是 [9]，右子树前序是 [20,15,7]。
4. 对左子树：前序 [9]，中序 [9] → 根节点 9，左右子树为空。
5. 对右子树：前序 [20,15,7]，中序 [15,20,7] → 根节点 20，左子树中序 [15]，右子树中序 [7]。
6. 递归直到所有节点处理完毕。

步骤 4：优化查找效率

• 每次在中序遍历中查找根节点位置时，如果直接线性扫描，最坏时间复杂度为 O(n²)。
• 优化：预先用哈希表存储中序遍历的值到索引的映射，将查找时间降为 O(1)。

步骤 5：代码实现细节

1. 初始化哈希表 inorderMap，存储中序遍历的值和索引。
2. 定义递归函数 build，参数为前序和中序的当前区间（用起始和结束索引表示）。
3. 递归终止条件：前序区间为空（即 preStart > preEnd）。
4. 通过哈希表快速定位根节点在中序中的位置，计算左子树大小。
5. 递归构建左右子树，连接至根节点。

步骤 6：复杂度分析

• 时间复杂度：O(n)，每个节点处理一次。
• 空间复杂度：O(n)，哈希表存储中序遍历索引，递归栈深度取决于树高。

通过以上步骤，可以系统性地构造出唯一的二叉树结构。