二叉树的后序遍历

记住「先左、再右、最后才记根」,记根的语句放在两个递归调用之后。下面逐帧走一遍这棵树。

后序遍历(左→右→根)：先看清这棵树:根是 50,它的左孩子 30(下面挂着 20、40)、右孩子 80(下面挂着 70)。后序遍历也从根 50 出发,但它要「左右子树都处理完才记根」,所以根 50 会是最后一个被记下的。

后序遍历(左→右→根)：递归进入节点 值50(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值50,先去把它的左、右子树处理完。

后序遍历(左→右→根)：递归进入节点 值30(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值30,先去把它的左、右子树处理完。

后序遍历(左→右→根)：递归进入节点 值20(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值20,先去把它的左、右子树处理完。

后序遍历(左→右→根)：值20 是叶子节点,没有左右孩子,左右子树都为空,这时把它记进结果(它变绿),现在结果是 [20]。

后序遍历(左→右→根)：值20 这棵子树全部遍历完毕,从递归里返回到上一层 值30。

后序遍历(左→右→根)：值30 的左子树整段都走完了,递归回到 值30。后序里左边完了还不能记根,先去它的右子树。

后序遍历(左→右→根)：递归进入节点 值40(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值40,先去把它的左、右子树处理完。

后序遍历(左→右→根)：值40 是叶子节点,没有左右孩子,左右子树都为空,这时把它记进结果(它变绿),现在结果是 [20, 40]。

后序遍历(左→右→根)：值40 这棵子树全部遍历完毕,从递归里返回到上一层 值30。

后序遍历(左→右→根)：值30 的右子树也走完了,递归回到 值30。左、右子树都处理完了,现在才轮到记根。

后序遍历(左→右→根)：值30 的左右子树都遍历完了,这时才把 值30 记进结果(它变绿),现在结果是 [20, 40, 30]。

后序遍历(左→右→根)：值30 这棵子树全部遍历完毕,从递归里返回到上一层 值50。

后序遍历(左→右→根)：值50 的左子树整段都走完了,递归回到 值50。后序里左边完了还不能记根,先去它的右子树。

后序遍历(左→右→根)：递归进入节点 值80(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值80,先去把它的左、右子树处理完。

后序遍历(左→右→根)：递归进入节点 值70(紫色)。后序的规矩是「根在最后」,所以一进来先不记 值70,先去把它的左、右子树处理完。

后序遍历(左→右→根)：值70 是叶子节点,没有左右孩子,左右子树都为空,这时把它记进结果(它变绿),现在结果是 [20, 40, 30, 70]。

后序遍历(左→右→根)：值70 这棵子树全部遍历完毕,从递归里返回到上一层 值80。

后序遍历(左→右→根)：值80 没有右孩子,右子树为空。左、右子树都处理完了,现在才轮到记根。

后序遍历(左→右→根)：值80 的左右子树都遍历完了,这时才把 值80 记进结果(它变绿),现在结果是 [20, 40, 30, 70, 80]。

后序遍历(左→右→根)：值80 这棵子树全部遍历完毕,从递归里返回到上一层 值50。

后序遍历(左→右→根)：值50 的右子树也走完了,递归回到 值50。左、右子树都处理完了,现在才轮到记根。

后序遍历(左→右→根)：值50 的左右子树都遍历完了,这时才把 值50 记进结果(它变绿),现在结果是 [20, 40, 30, 70, 80, 50]。

后序遍历(左→右→根)：值50 是根,它的整棵树都遍历完了,递归回到最外层,后序遍历到此结束。

后序遍历(左→右→根)：整棵树后序遍历完成,结果是 20、40、30、70、80、50。回头看:每到一个节点都「先左、再右、最后才记自己」,所以根 50 最后才出现;递归栈帮我们记住回溯路径,每个节点恰好访问一次,所以是 O(n)。

边界:空树返回空、单节点只记根、退化链空间退化成 O(n)。

两个高频追问:迭代用「根右左再反转」;后序适合先算子树再算根的场景。