LeetCode 889. 从前序与后序遍历序列构造二叉树
题目描述
题意分析
给出同一棵二叉树的前序、后序遍历，节点值互不相同，构造任意一棵能产生这两份遍历结果的树。题目保证输入有效，不要求还原唯一树形。
前序顺序是根、左子树、右子树，后序顺序是左子树、右子树、根。缺少中序时，某个节点的唯一孩子究竟在左边还是右边可能无法判断；把这种唯一孩子统一放左边，也能得到合法答案。
解法：递归切分遍历区间
核心思路
[!blue]
用
build(preLeft, postLeft, size)构造同一棵子树：它在前序中从preLeft开始，在后序中从postLeft开始，两段都包含size个节点。前序第一项就是当前根，后序最后一项也对应这个根。当
size > 1，前序的下一项是第一个被访问的孩子子树的根。若当前根有两个孩子，它必然是左子树根；若只有一个孩子，也统一把这棵子树作为左子树。因此可以用preorder[preLeft + 1]定位待构造的左子树。在后序遍历中，这棵左子树的全部节点连续出现在当前区间开头，而左子树根排在它们最后。找到该根的后序下标
index后，左子树大小就是闭区间长度index - postLeft + 1。节点值互异，预先建立后序值到下标的映射，就能直接定位，不必每层重新扫描。左子树的前序从当前根之后开始，后序仍从
postLeft开始；右子树的两份遍历都要跳过整个左子树。于是右侧前序起点为preLeft + 1 + leftSize，后序起点为postLeft + leftSize，长度为size - 1 - leftSize，减去的额外一个节点就是当前根。如果
leftSize == size - 1，说明第一个孩子已经占据全部剩余节点，右子树为空。把唯一孩子放左边不会改变前序或后序顺序，因此仍符合输入。递归中size == 0返回空，size == 1创建根后直接返回，避免再读取不存在的下一项。每层都按同一组节点切出左右两段，再递归连接到根，两份遍历的对应关系就被逐层保持，最终得到一棵符合要求的树。
解题步骤
- 建立后序遍历中“节点值 → 下标”的映射。
- 从两个起点均为
0、长度为节点总数开始构造。- 空区间返回空；否则以前序首项创建根，若只有一个节点则直接返回。
- 查找前序下一项在后序中的位置，计算
leftSize = index - postLeft + 1。- 左侧从
(preLeft + 1, postLeft)开始构造leftSize个节点。- 右侧从
(preLeft + 1 + leftSize, postLeft + leftSize)开始，构造剩余的size - 1 - leftSize个节点，再返回根。
代码实现
class Solution {
private int[] preorder;
private Map<Integer, Integer> postIndex;
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
this.preorder = preorder;
postIndex = new HashMap<>();
for (int i = 0; i < postorder.length; i++) {
postIndex.put(postorder[i], i);
}
return build(0, 0, preorder.length);
}
// 两段遍历从各自起点取同样数量，描述一棵子树
private TreeNode build(int preLeft, int postLeft, int size) {
if (size == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[preLeft]);
// 单节点无需再读前序下一项
if (size == 1) {
return root;
}
int leftRootIndex = postIndex.get(preorder[preLeft + 1]);
// 后序中的闭区间长度确定左子树规模
int leftSize = leftRootIndex - postLeft + 1;
root.left = build(preLeft + 1, postLeft, leftSize);
// 右侧长度扣除当前根与整棵左子树
root.right = build(preLeft + 1 + leftSize, postLeft + leftSize, size - 1 - leftSize);
return root;
}
}
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
postIndex := make(map[int]int, len(postorder))
for i, value := range postorder {
postIndex[value] = i
}
var build func(preLeft, postLeft, size int) *TreeNode
// 两段遍历从各自起点取同样数量，描述一棵子树
build = func(preLeft, postLeft, size int) *TreeNode {
if size == 0 {
return nil
}
root := &TreeNode{Val: preorder[preLeft]}
// 单节点无需再读前序下一项
if size == 1 {
return root
}
leftRootIndex := postIndex[preorder[preLeft+1]]
// 后序中的闭区间长度确定左子树规模
leftSize := leftRootIndex - postLeft + 1
root.Left = build(preLeft+1, postLeft, leftSize)
// 右侧长度扣除当前根与整棵左子树
root.Right = build(
preLeft+1+leftSize,
postLeft+leftSize,
size-1-leftSize,
)
return root
}
return build(0, 0, len(preorder))
}
复杂度分析
- 时间复杂度：期望 $O(n)$，建表与构造各处理节点一次。
- 空间复杂度：$O(n)$，索引表加递归栈，不计结果树。
关键点总结
[!green]
- 两段描述同一棵子树：前后序各自起点不同，但节点数量必须一致。
- 后序的子树根决定区间末端：它的位置连同当前后序起点确定左子树大小。
- 单孩子方向不必唯一还原：统一放左侧只是选取一种符合遍历结果的树形。
- 使用下标避免反复复制：递归传入起点和长度，索引表负责常数时间定位。
易错点总结
[!yellow]
- 左子树长度漏加一：后序区间包含左子树根本身，应按闭区间计算。
- 右侧长度只减左子树：还要扣除当前根，才能让两侧与根的节点总数恰好等于
size。- 单节点仍读取前序下一项：可能越界或误读其他子树，应先处理叶子边界。
- 右侧两个起点都加一：前序需要跳过当前根，后序的根位于末尾，所以后序起点只跳过左子树。
- 要求唯一孩子必须还原到原方向：仅凭前后序无法确定这一点，返回任意合法结果即可。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 105. 从前序与中序遍历序列构造二叉树 | 中等 | 有中序时左右子树划分更直接且可唯一还原，本题只给前序和后序，单孩子方向可能不唯一。 |
| 106. 从中序与后序遍历序列构造二叉树 | 中等 | 同样由遍历序列恢复树，本题缺少中序，需按前序的下一根在后序中的位置划分。 |