题目描述
思路解析
一句话答案：LeetCode 590 N 叉树的后序遍历：每个节点先把孩子从左到右递归走完，最后才收自己，一趟递归 DFS 就能排出整条后序序列，时间 O(n)、空间 O(h)。
后序遍历要返回一串什么样的顺序
给一棵 N 叉树的根节点 root，把所有节点的值按后序排成一个列表返回。N 叉树就是每个节点的孩子不止两个，而是存在一个孩子列表里，从左到右排好。题面示例 root=[1,null,3,2,4,null,5,6]，画出来是根 1 底下挂着 3、2、4 三个孩子，3 又带着 5、6，最后要返回 [5,6,3,2,4,1]。
先收根、再走孩子，序列会歪成什么样
不少人第一笔就把根 1 写进结果，再去处理孩子——这样收出来的是 [1,3,5,6,2,4]，根跑到了最前头，正是前序而不是后序。后序的定义卡得很死：一个节点的值，必须等它名下所有孩子、连同孩子的孩子都进了结果，才轮得到它自己。收根的时机差一步，整串顺序就全歪了。
孩子全收完，才轮到收自己
把这条规矩摊开来看：站在任意一个节点上，先别急着收自己，而是照孩子列表从左到右，一个个钻下去递归。等某个孩子是叶子、底下再没有孩子了，它就能直接进结果；要等这个节点名下的孩子全部落进结果，才排得上收它自己的值。二叉树的后序是先左右两个孩子再收自己，N 叉树只是把『两个孩子』换成『一整个孩子列表』，规矩一模一样。
一个 dfs 在每个节点做的三件事
写成递归就是一个 dfs(node)：先判空，node 为空直接返回，空树和走到底都靠它兜住；再用 for 循环，按顺序对 node.children 里的每个孩子递归调用 dfs；等这个 for 循环整个跑完、所有孩子都收完了，才把 node.val 追加进答案数组 ans。这三步的先后不能乱——append 自己这一步，永远排在 for 循环之后。
拿 [1,null,3,2,4,null,5,6] 从头收到尾
从根 1 进 dfs。1 的孩子是 3、2、4，先钻第一个孩子 3。3 的孩子是 5、6，又先钻 5：5 没有孩子，直接进结果，ans=[5]；回到 3 收第二个孩子 6，6 也没孩子，ans=[5,6]；3 的孩子收完，收 3 自己，ans=[5,6,3]。回到 1 的第二个孩子 2，没孩子，ans=[5,6,3,2]；第三个孩子 4，没孩子，ans=[5,6,3,2,4]；1 的三个孩子全收完，最后收根 1，ans=[5,6,3,2,4,1]，和题面输出一致。
先把根收了，后序当场变前序
最爱出岔子的是收根的时机：把 append 自己写在 for 循环前头，根提前入了列，后序当场退化成前序。孩子顺序也不能乱，从右往左递归会让同层孩子的相对次序整个颠倒。还有空节点，忘了判空、遇到空树就直接越界报错。复杂度这边倒是干净：每个节点只被处理一回，时间 O(n)；额外开销是递归栈，深度等于当前走到的层数，最多就是树高 h，空间 O(h)，最坏树退化成一条链时 h=n。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「先遍历孩子列表、最后收根」这一条,下面每一帧都在套它。
准备 · 从根出发：开局后序序列为空。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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题