题目描述
思路解析动画文字版
不能。单看中序 [9,3,15,20,7],你不知道谁是根——树可以有很多种长法,中序结果一样。必须再给一串顺序当「定位器」。
后序是「左→右→根」,根永远最后访问。所以后序末尾那个数,就是当前这棵(子)树的根。这是第一把钥匙。
中序是「左→根→右」,所以根在中序里的位置,天然把数组切成两半:左半边是左子树的全部节点,右半边是右子树的全部。这是第二把钥匙。
盯三样东西:后序从右往左一个个被取走当根、中序区间被根切成左右两段、下方那棵树一格一格长出来。
后序末尾 = 整棵树的根：先看后序 [9,15,7,20,3]。末尾的 3 是整棵树的根。取走它,后续在剩下的 [9,15,7,20] 里继续找子树的根。
回中序定位根 3：拿着根 3 回到中序 [9,3,15,20,7],它在下标 1。它左边 [9](下标 [0,0])是左子树,右边 [15,20,7](下标 [2,4])是右子树。
根诞生 · 3：第一个节点 3 出现,它是整棵树的根。后序的递归约定是先建右子树(因为根从后往前取,右边的根先冒出来),所以下一步先去搭 3 的右子树 [2,4]。
再取后序末尾 → 右子树的根：根 3 取走后,后序还剩 [9,15,7,20]。新的末尾 20 就是 3 右子树的根。后序末尾总是「下一个要挂的根」。
回中序定位根 20：在中序的右段 [2,4] 里找 20,它在下标 3。于是 20 把这段切成:左边 [15](下标 [2,2])、右边 [7](下标 [4,4])。左边已用掉的 [9,3] 灰掉了。
挂右孩子 · 20：20 挂到 3 的右下方。它自己又有左右两段要建,同样先建右 [4,4]、再建左 [2,2]。
再取后序末尾 → 20 的右孩子：20 取走后,后序剩 [9,15,7],末尾 7。它对应中序右段 [4,4],只有一个数,所以 7 是个叶子。
回中序定位根 7：中序区间缩到只剩 [4,4] 一个数 7。单个元素就是叶子:它左右都空,挂为 20 的右孩子后,这一支就到底了。
挂叶子 · 7：7 落在 20 的右下角,是片叶子。20 的右边搞定,函数回头处理 20 的左段 [2,2]。
再取后序末尾 → 20 的左孩子：7 取走后,后序剩 [9,15],末尾 15。它对应中序左段 [2,2],也只有一个数,又是叶子。
回中序定位根 15：中序区间缩到 [2,2],只剩 15。它挂为 20 的左孩子。到这里 20 的左右孩子都齐了,3 的整棵右子树建完。
挂叶子 · 15：15 落在 20 的左下角。根 3 的整棵右子树建好了,函数才回头去建 3 的左段 [0,0]。
最后取后序末尾 → 3 的左孩子：后序只剩最后一个 9,它对应中序左段 [0,0]。这是 3 的左孩子,也是最后一个待安家的数。
回中序定位根 9：中序区间缩到 [0,0],只剩 9。它挂为 3 的左孩子。所有 5 个数都要安家了。
挂叶子 · 9：9 落在 3 的左下角。后序从右往左一个个取根、中序每次切左右段,5 个数一格一格全长进了树里。
建树完成：树还原完成:根 3,左孩子 9,右孩子 20;20 再带 15 和 7。和题目给的标准输出 [3,9,20,null,null,15,7] 完全一致。
验证 · 中序遍历：先按「左→根→右」验一遍。一路往左走到底,最先访问最左的 9。中序结果应当和原 inorder 一字不差。
验证 · 中序遍历：9 没有孩子,回到它的父节点、也是整棵树的根 3。已亮的 9 变灰,当前点亮 3。接着去走 3 的右子树。
验证 · 中序遍历：进入右子树,先走到它的最左 15(20 的左孩子)。到这里序列是 9 → 3 → 15,和原 inorder 前三个对得上。
验证 · 中序遍历：再访问 15 的父 20、最后它的右孩子 7。完整中序 9 → 3 → 15 → 20 → 7,和原 inorder 分毫不差。
验证 · 后序遍历：再按「左→右→根」走一遍:9 → 15 → 7 → 20 → 3,正好等于原后序数组。两种遍历都对上,说明我们建的树分毫不差。
因为每次都从后序末尾弹一个数当根,而末尾紧挨着的是「右子树的根」。要让弹出的顺序对上,代码里就得先 build(右) 再 build(左)。顺序反了,树就会错。
凡是「给两种遍历还原树」的题(LC105 前序+中序、本题后序+中序)都是这一招:一种序列提供根,中序提供左右边界。想通这点,这一类题就全通了。
雷区实演 · 左右顺序反了：若代码先 build(左),会把本该当右孩子的 20 错挂成左孩子,9、20 左右颠倒,整棵树全错。后序题必须先右后左。
边界三连：递归出口 lo>hi 同时兜住「空树」和「叶子的左右空区间」两种情况。
面试追问：哈希表提速、与 LC105 的对称、值唯一前提,是这题面试最常被追的三点。
参考代码
class Solution: def buildTree(self, inorder, postorder): idx = {v: i for i, v in enumerate(inorder)} # 值→中序下标 def build(lo, hi): if lo > hi: # 中序区间为空 → 无节点 return None val = postorder.pop() # 后序末尾 = 当前根 root = TreeNode(val) mid = idx[val] # 根在中序里的位置 root.right = build(mid + 1, hi) # 先建右子树 root.left = build(lo, mid - 1) # 再建左子树 return root return build(0, len(inorder) - 1)复杂度
- 时间复杂度：O(n)，用哈希表 O(1) 定位根,每个节点只建一次,共 n 个 → O(n)
- 空间复杂度：O(n)，哈希表 O(n) + 递归栈最深 O(n)(树退化成链时)
易错点
面试追问把动画讲成自己的话
追问为什么时间能做到 O(n)?
追问和 LC105(前序+中序)有何区别?
追问为什么节点值必须互不相同?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
有序链表转换二叉搜索树
LeetCode 109 · 中等 · 沿着 二叉树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题