二叉树遍历 · 单步演示
后序遍历
先后序遍历左子树，再后序遍历右子树，最后访问根。一个结点总是在它所有子孙都处理完之后才被访问。
调用栈（底 → 顶）（空）
后序序列（空）
步 001 / 057后序遍历：先左子树，再右子树，最后访问根。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
遍历(node)：if node 为空：return遍历(node.left)遍历(node.right)访问 node
变量
| node | 空 |
|---|---|
| 递归深度 | 0 |
| 已输出 | [] |
复杂度
| 最好情况 | O(n) |
|---|---|
| 平均情况 | O(n) |
| 最坏情况 | O(n) |
| 额外空间 | O(h) |
每个结点访问一次；调用栈深度等于树高 h。
要点
- 释放一棵树的内存、计算每棵子树的大小或高度，都要先处理孩子，用后序。
- 后序序列的最后一个元素一定是根。
常见错误
用非递归写后序比前序、中序都麻烦：需要记住右子树是否已经处理过，否则会重复进入。