Problem: 105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
【LeetCode 热题 100】105. 从前序与中序遍历序列构造二叉树——（解法一）O（n^2）
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(N)
整体思路
这段代码同样旨在解决 “从前序与中序遍历序列构造二叉树” 的问题。与上一个通过复制子数组的解法相比，此版本采用了哈希表和指针/索引来界定子数组范围，从而极大地优化了时空效率，是解决此问题的标准最优解法。
算法的核心思想依然是基于前序和中序遍历性质的分治法，但实现细节完全不同：
-
预处理：哈希表加速查找
- 算法首先创建一个哈希表
index，用于存储中序遍历中每个元素值及其对应的索引。 - 目的：这一步是性能优化的关键。它将“在中序遍历中查找根节点位置”这个操作的时间复杂度从 O(N) 降到了 O(1)。
- 算法首先创建一个哈希表
-
通过索引定义子问题
- 算法不再通过
Arrays.copyOfRange来创建新的子数组，而是定义了一个辅助的dfs函数，它接收多个索引参数来界定当前需要处理的子数组范围。 dfs(preorder, preL, preR, inL, inR, index):preL,preR: 定义了当前子树在前序遍历数组preorder中的范围[preL, preR)(左闭右开)。inL,inR: 定义了当前子树在中序遍历数组inorder中的范围[inL, inR)。
- 这种方式避免了任何数组复制，所有操作都在原始数组上进行。
- 算法不再通过
-
递归构造逻辑
dfs函数的执行流程如下：
a. 基线条件：if (preL == preR)，如果范围为空，说明子树为空，返回null。
b. 确定根节点：当前子树的根节点值是preorder[preL]。
c. 分割子树 (O(1) 操作)：- 使用预处理好的哈希表
index.get(preorder[preL])，瞬间（O(1)时间）找到根节点在中序遍历中的位置，记为inRootIndex。 - 计算左子树的大小
leftSize = inRootIndex - inL。
d. 递归构建左右子树： - 左子树：
* 前序范围是[preL + 1, preL + 1 + leftSize)
* 中序范围是[inL, inL + leftSize)
* 递归调用dfs(...)构建左子节点left。 - 右子树：
* 前序范围是[preL + 1 + leftSize, preR)
* 中序范围是[inL + 1 + leftSize, inR)
* 递归调用dfs(...)构建右子节点right。
e. 合并结果：创建新的TreeNode，连接上一步构造出的left和right子节点，并返回。
- 使用预处理好的哈希表
通过哈希表和索引范围，该算法将每一步递归中的核心操作都优化到了 O(1)，从而实现了整体的线性时间复杂度。
完整代码
class Solution {/*** 根据前序遍历和中序遍历的结果，构造二叉树（优化版）。* @param preorder 前序遍历数组* @param inorder 中序遍历数组* @return 构造出的二叉树的根节点*/public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 步骤 1: 预处理，用哈希表存储中序遍历中值到索引的映射，以实现 O(1) 查找。Map<Integer, Integer> index = new HashMap<>(n);for (int i = 0; i < n; i++) {index.put(inorder[i], i);}// 调用辅助的 DFS 函数开始递归构建return dfs(preorder, 0, n, 0, n, index);}/*** 辅助 DFS 函数，通过索引范围在原数组上构建子树。* @param preorder 完整的前序遍历数组* @param preL 当前子树在前序数组中的左边界（包含）* @param preR 当前子树在前序数组中的右边界（不包含）* @param inL 当前子树在中序数组中的左边界（包含）* @param inR 当前子树在中序数组中的右边界（不包含）* @param index 中序遍历值到索引的映射哈希表* @return 构建好的子树的根节点*/private TreeNode dfs(int[] preorder, int preL, int preR, int inL, int inR, Map<Integer, Integer> index) {// 递归的基线条件：如果范围为空，则子树为空。if (preL == preR) {return null;}// 根节点的值是前序遍历范围的第一个元素int rootVal = preorder[preL];// O(1) 时间从中序哈希表中获取根节点的位置int inRootIndex = index.get(rootVal);// 计算左子树的大小int leftSize = inRootIndex - inL;// 递归构建左子树// 左子树的前序范围：[preL + 1, preL + 1 + leftSize)// 左子树的中序范围：[inL, inRootIndex) (即 inL + leftSize)TreeNode left = dfs(preorder, preL + 1, preL + 1 + leftSize, inL, inRootIndex, index);// 递归构建右子树// 右子树的前序范围：[preL + 1 + leftSize, preR)// 右子树的中序范围：[inRootIndex + 1, inR)TreeNode right = dfs(preorder, preL + 1 + leftSize, preR, inRootIndex + 1, inR, index);// 创建根节点，连接左右子树，并返回return new TreeNode(rootVal, left, right);}
}
时空复杂度
时间复杂度：O(N)
- 哈希表预处理：
for循环遍历inorder数组一次，构建哈希表。时间复杂度为 O(N)。 - 递归构建：
dfs函数会对preorder数组中的每个元素处理一次（作为一次根节点）。- 在
dfs函数内部，所有的操作——哈希表查找、算术运算、创建新节点——都是 O(1) 的。 - 由于每个节点只被访问一次，总的递归构建时间为
N * O(1)= O(N)。
- 在
综合分析：
总时间复杂度 = 预处理时间 + 递归构建时间 = O(N) + O(N) = O(N)。
空间复杂度：O(N)
- 哈希表：算法创建了一个哈希表
index来存储中序遍历的映射。在最坏情况下，所有元素都不同，哈希表需要存储N个键值对。因此，哈希表占用的空间为 O(N)。 - 递归调用栈：递归的深度取决于树的高度
H。- 在最好的情况下（一个完全二叉树），
H约为log N，递归栈空间为 O(log N)。 - 在最坏的情况下（一个极度倾斜的链状树），
H等于N，递归栈空间为 O(N)。
- 在最好的情况下（一个完全二叉树），
综合分析：
算法所需的额外空间由哈希表和递归调用栈共同决定。总空间复杂度为 O(N) (哈希表) + O(H) (递归栈)。由于 H 的上界是 N，因此最坏情况下的总空间复杂度为 O(N) + O(N) = O(N)。
参考灵神
详解)
