题目描述
思路解析动画文字版
记住「先遍历孩子列表、最后收根」这一条,下面每一帧都在套它。
准备 · 从根出发：开局后序序列为空。DFS 从根节点 50 出发,口诀是先把孩子走完再收自己,我们一路往下探。
下行 · 进入 50：走到节点 50(紫色)。它的孩子列表是 30、80,按后序规矩,要先把这些孩子从左到右一个个递归走完,50 自己留到最后再收。
下行 · 进入 30：走到节点 30(紫色)。它的孩子列表是 10、20,按后序规矩,要先把这些孩子从左到右一个个递归走完,30 自己留到最后再收。
下行 · 进入 10：走到节点 10(紫色)。它的孩子列表是 15、25,按后序规矩,要先把这些孩子从左到右一个个递归走完,10 自己留到最后再收。
下行 · 到叶子 15：走到节点 15(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
回收 · 收下叶子 15：叶子 15 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15。
下行 · 到叶子 25：走到节点 25(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
回收 · 收下叶子 25：叶子 25 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15 25。
回收 · 收下 10：10 的孩子 15、25 都已经收完了,现在轮到 10 自己。把 10 追加进后序序列(变绿),目前序列是 15 25 10。
下行 · 到叶子 20：走到节点 20(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
回收 · 收下叶子 20：叶子 20 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15 25 10 20。
回收 · 收下 30：30 的孩子 10、20 都已经收完了,现在轮到 30 自己。把 30 追加进后序序列(变绿),目前序列是 15 25 10 20 30。
下行 · 进入 80：走到节点 80(紫色)。它的孩子列表是 70、90,按后序规矩,要先把这些孩子从左到右一个个递归走完,80 自己留到最后再收。
下行 · 进入 70：走到节点 70(紫色)。它的孩子列表是 75、78,按后序规矩,要先把这些孩子从左到右一个个递归走完,70 自己留到最后再收。
下行 · 到叶子 75：走到节点 75(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
回收 · 收下叶子 75：叶子 75 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15 25 10 20 30 75。
下行 · 到叶子 78：走到节点 78(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
回收 · 收下叶子 78：叶子 78 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15 25 10 20 30 75 78。
回收 · 收下 70：70 的孩子 75、78 都已经收完了,现在轮到 70 自己。把 70 追加进后序序列(变绿),目前序列是 15 25 10 20 30 75 78 70。
下行 · 到叶子 90：走到节点 90(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
回收 · 收下叶子 90：叶子 90 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15 25 10 20 30 75 78 70 90。
回收 · 收下 80：80 的孩子 70、90 都已经收完了,现在轮到 80 自己。把 80 追加进后序序列(变绿),目前序列是 15 25 10 20 30 75 78 70 90 80。
回收 · 收下 50：50 的孩子 30、80 都已经收完了,现在轮到 50 自己。把 50 追加进后序序列(变绿),目前序列是 15 25 10 20 30 75 78 70 90 80 50。
完成 · 后序序列：整棵树走完,所有节点都收进了后序序列:15 25 10 20 30 75 78 70 90 80 50。可以看到每个节点都在自己的孩子全部收完之后才入列,根 50 排在最后,这就是后序的特征。
边界先想清:空树返回空;单节点返回它自己;一层孩子全是叶子时,孩子按从左到右收完,最后收根。
面试重点:迭代法用「改良前序加反转」,以及空间为什么是树高 O(h)。
参考代码
from typing import Listclass Node: def __init__(self, val=None, children=None): self.val = val self.children = children if children is not None else []class Solution: def postorder(self, root: 'Node') -> List[int]: ans = [] def dfs(node): if not node: return for child in node.children: dfs(child) ans.append(node.val) dfs(root) return ans复杂度
- 时间：O(n)，每个节点恰好被访问一次:进入一次、收一次,n 个节点就是 O(n)
- 空间：O(h)，递归栈深度等于树高 h;最坏退化成一条链时 h = n,即 O(n)
易错点
面试追问把动画讲成自己的话
追问进阶要求用迭代法,怎么做?
追问为什么递归空间是 O(h) 而不是 O(n)?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树的层平均值
LeetCode 637 · 简单 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题