LeetCode 105. 从前序与中序遍历序列构造二叉树
题目描述
题意分析
preorder和inorder分别是同一棵二叉树的前序、中序遍历结果，需要重新创建这棵树并返回根节点。前序按“根、左子树、右子树”访问，中序按“左子树、根、右子树”访问。题目保证两个序列合法且节点值互不相同，因此它们能够唯一确定原树。这里是普通二叉树，不要求满足二叉搜索树的大小关系；判断一个节点属于哪棵子树，要看它在遍历序列中的位置，不能比较数值大小。
解法：递归切分前序与中序区间
核心思路
[!blue]
单看前序可以知道根是谁，却不知道左右子树各有多少节点；中序能够按根的位置划分左右子树，却不会标明哪个元素是根。把两种信息结合起来：用前序首元素确定当前根，再到中序中找到它，根左边就是整棵左子树，右边就是整棵右子树。
定义
build(preRoot, inLeft, inRight)：当前子树的根位于前序下标preRoot，它的全部节点位于中序闭区间[inLeft, inRight]。每次递归都保持这两个描述指向同一棵子树，因此不必再传前序终点，也不必复制子数组。设当前根在中序中的下标为
rootIdx，左子树节点数就是leftSize = rootIdx - inLeft。由于前序中先访问根，再连续访问整棵左子树，最后连续访问右子树，两个递归调用的范围就确定了：
- 左子树的前序根紧跟当前根，位于
preRoot + 1；中序区间为[inLeft, rootIdx - 1]。- 右子树的前序根要跳过当前根和
leftSize个左子树节点，位于preRoot + leftSize + 1；中序区间为[rootIdx + 1, inRight]。每次切分都去掉当前根，并把其余节点准确分给左右子树。递归分别还原这两个更小的问题，再接回当前根，就能还原整棵树。当
inLeft > inRight时区间为空，应先返回空节点，不能再读取前序数组；只有一个节点的区间则会正常建出叶子。节点值不重复，可以提前建立“节点值到中序下标”的哈希表，让每次找根只需平均
O(1)时间。这样即使树退化成链，也不需要反复扫描整个剩余中序区间。
解题步骤
- 遍历
inorder，建立每个节点值对应的中序下标映射。- 从前序根下标
0和中序区间[0, n - 1]开始递归。- 若中序区间为空，返回空节点；否则以
preorder[preRoot]创建当前根。- 查出
rootIdx，计算leftSize = rootIdx - inLeft，按左右子树各自的前序根和中序区间递归。- 将两个递归结果分别接到当前根的左右孩子，返回当前根。
代码实现
class Solution {
private Map<Integer, Integer> indexMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
indexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
indexMap.put(inorder[i], i);
}
return build(preorder, 0, 0, inorder.length - 1);
}
// 前序根下标与中序闭区间描述同一子树，空区间要先于前序取值处理。
private TreeNode build(int[] preorder, int preRoot, int inLeft, int inRight) {
if (inLeft > inRight) {
return null;
}
int rootVal = preorder[preRoot];
TreeNode root = new TreeNode(rootVal);
int rootIdx = indexMap.get(rootVal);
// 中序区间内根的左侧节点数，决定前序中的右子树起点。
int leftSize = rootIdx - inLeft;
root.left = build(preorder, preRoot + 1, inLeft, rootIdx - 1);
// 跳过当前根和整棵左子树，才到右子树的前序根。
root.right = build(preorder, preRoot + leftSize + 1, rootIdx + 1, inRight);
return root;
}
}
func buildTree(preorder []int, inorder []int) *TreeNode {
indexMap := make(map[int]int)
for i, num := range inorder {
indexMap[num] = i
}
var build func(preRoot, inLeft, inRight int) *TreeNode
// 前序根下标与中序闭区间描述同一子树，空区间要先于前序取值处理。
build = func(preRoot, inLeft, inRight int) *TreeNode {
if inLeft > inRight {
return nil
}
rootVal := preorder[preRoot]
root := &TreeNode{Val: rootVal}
rootIdx := indexMap[rootVal]
// 中序区间内根的左侧节点数，决定前序中的右子树起点。
leftSize := rootIdx - inLeft
root.Left = build(preRoot+1, inLeft, rootIdx-1)
// 跳过当前根和整棵左子树，才到右子树的前序根。
root.Right = build(preRoot+leftSize+1, rootIdx+1, inRight)
return root
}
return build(0, 0, len(inorder)-1)
}
复杂度分析
设节点数为 $n$，树高为 $h$。
- 时间复杂度：$O(n)$。建立映射和创建节点都只遍历一次，每个节点的根位置查询平均为 $O(1)$。
- 辅助空间复杂度：$O(n)$。哈希表占 $O(n)$，递归栈占 $O(h)$，树退化成链时 $h=n$；不计返回的树节点占用的空间。
关键点总结
[!green]
- 前序确定根，中序确定左右子树的归属，节点数量再确定前序中的子树起点。
preRoot与中序闭区间必须始终描述同一棵子树。- 节点值互异保证中序位置唯一，传下标和查哈希表可以避免重复扫描、复制数组。
易错点总结
[!yellow]
rootIdx是整份中序数组的下标，左子树大小要减去当前区间起点inLeft，不能直接使用rootIdx。- 右子树的前序根下标为
preRoot + leftSize + 1；漏加当前根占用的1会把左右子树范围错开。- 空区间判断是
inLeft > inRight，不是>=；相等时仍有一个节点。- 必须先判断区间为空，再访问
preorder[preRoot]，因为空子树对应的前序起点可能已经到达数组末尾。- 划分中序时要排除当前根，否则子问题无法持续缩小；也不能把普通二叉树当成二叉搜索树按值大小切分。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 106. 从中序与后序遍历序列构造二叉树 | 中等 | 中序仍负责划分左右子树，原题从后序末尾取根，本题从前序开头取根。 |
| 889. 从前序与后序遍历序列构造二叉树 | 中等 | 只给前序和后序可能无法唯一确定左右孩子，本题有中序且值互异时分割位置唯一。 |