LeetCode 106. 从中序与后序遍历序列构造二叉树
目录
题目描述
题意分析
给定同一棵二叉树的中序遍历序列
inorder与后序遍历序列postorder，还原出这棵树并返回根节点。题目保证两个序列长度相同、且所有节点的值互不相同。这个保证不是可有可无的修饰：正因为值不重复，任何一个值在中序序列中的位置才是唯一确定的，否则同一组序列可能对应多棵不同的树，问题本身就无解。
约束里节点数不超过 3000，$O(n^2)$ 的做法能过，但一棵退化成链的斜树会让「每层都线性查找根的位置」稳定顶到上界，同时递归深度也会达到 $n$。这两点提示实现时既要压查找开销，也要意识到栈深的风险。
需要留意的边界情形：序列为空时返回空树；只有一个节点；整棵树只有左孩子或只有右孩子的斜树；某个节点只有单侧孩子，此时另一侧的递归区间为空。
解法：哈希表定位根节点递归建树
核心思路
问题关键：后序遍历是“左、右、根”，末尾能确定根；中序遍历是“左、根、右”，根的位置能确定两棵子树的边界。题目保证值互不相同，因此可以用哈希表唯一定位根。
为什么选倒序后序 + 中序区间：倒着读取后序序列，顺序恰好是“根、右、左”。用一个递减的
postIndex取根，只需给递归传中序区间，比同时维护四个区间端点更短；哈希表把每次定位根从 $O(n)$ 降为 $O(1)$。递归契约：
build(inLeft, inRight)构造中序区间[inLeft,inRight]对应的子树；调用开始时，postIndex指向这棵子树的根。取根后必须先递归右区间，再递归左区间，以匹配后序的倒序读取顺序。正确性：根值来自当前后序末端，在中序中的唯一位置把节点集合准确分成左右子树。先构造右树会消耗倒序后序中的右子树片段，随后左树正好读取自己的片段。对子树规模归纳，两个递归调用都能正确还原，连接到根后整棵树也正确。
解题步骤
- 建立“节点值 → 中序下标”的哈希表，并令
postIndex = postorder.length - 1。inLeft > inRight表示空子树，直接返回空节点。- 用
postorder[postIndex--]创建根，查表得到它在中序中的分界位置。- 先递归构造
[rootIndex+1,inRight]的右子树，再构造[inLeft,rootIndex-1]的左子树。口述样例：
inorder = [9,3,15,20,7]、postorder = [9,15,7,20,3]。先取根3，中序将其分为[9]和[15,20,7]；倒序后序接下来是右树根20，再依次构造7、15，最后构造左树9。
代码实现
class Solution {
private Map<Integer, Integer> indexMap;
private int[] postorder;
private int postIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
indexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
indexMap.put(inorder[i], i);
}
postIndex = postorder.length - 1;
return build(0, inorder.length - 1);
}
private TreeNode build(int inLeft, int inRight) {
if (inLeft > inRight) {
return null;
}
int rootVal = postorder[postIndex--];
TreeNode root = new TreeNode(rootVal);
int rootIndex = indexMap.get(rootVal);
root.right = build(rootIndex + 1, inRight);
root.left = build(inLeft, rootIndex - 1);
return root;
}
}
func buildTree(inorder []int, postorder []int) *TreeNode {
indexMap := make(map[int]int)
for i, value := range inorder {
indexMap[value] = i
}
postIndex := len(postorder) - 1
var build func(int, int) *TreeNode
build = func(inLeft int, inRight int) *TreeNode {
if inLeft > inRight {
return nil
}
rootVal := postorder[postIndex]
postIndex--
root := &TreeNode{Val: rootVal}
rootIndex := indexMap[rootVal]
root.Right = build(rootIndex+1, inRight)
root.Left = build(inLeft, rootIndex-1)
return root
}
return build(0, len(inorder)-1)
}
复杂度分析
- 时间复杂度：$O(n)$。建表和构造各遍历每个节点一次，查表均摊 $O(1)$。
- 空间复杂度：$O(n)$。哈希表占 $O(n)$，递归栈为 $O(h)$，最坏树高
h = n；返回树不计入额外空间。
关键点总结
- 后序末尾定根，中序位置划分左右子树，这是唯一性来源。
- 倒序读取后序时顺序是“根、右、左”，所以代码必须先建右树。
- 哈希表依赖“节点值互不相同”；有重复值时，两组遍历不足以唯一还原。
- 传中序下标而不是复制子数组，避免额外的 $O(n^2)$ 搬运。
易错点总结
- 使用递减的
postIndex却先建左树，会让左树误取右树的节点；样例中的20会被挂到错误一侧。- 递归出口必须是
inLeft > inRight；写成>=会丢掉所有单节点子树。- 根应取
postorder[postIndex]而非数组开头，并且每创建一个节点只递减一次。- 不要忽略值唯一的前提：重复值会让哈希表覆盖下标，且原问题本身通常不再有唯一答案。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 105. 从前序与中序遍历序列构造二叉树 | 中等 | 根取自前序开头而非后序末尾，前序指针从左往右推进，左右子树的区间推导方向与本题相反 |
| 889. 从前序与后序遍历序列构造二叉树 | 中等 | 缺少中序序列，单孩子节点的左右归属无法区分，答案不唯一，只需返回任意一棵 |
| 1008. 前序遍历构造二叉搜索树 | 中等 | 只给一个序列，靠二叉搜索树的值域上下界代替中序序列来划分左右子树 |
| 108. 将有序数组转换为二叉搜索树 | 简单 | 输入本身就是中序序列，可自由取中点为根以保证平衡，不需要第二个序列定根 |
| 109. 有序链表转换二叉搜索树 | 中等 | 与 108 题同思路，但链表无法随机访问，需用快慢指针找中点或先转成数组 |
| 449. 序列化和反序列化二叉搜索树 | 中等 | 反向问题，序列格式由自己设计，考点在于如何编码才能既紧凑又可还原 |
| 剑指 Offer 07. 重建二叉树 | 中等 | 与 105 题同题，可用来对照检验前序版本的下标推导是否写对 |
| 面试题 04.02. 最小高度树 | 简单 | 与 108 题同题，只要求树高最小，不要求还原某棵特定形状的树 |