二叉树的前序遍历

记住「先记根,再左,再右」,递归栈负责回溯。下面逐帧走一遍这棵树。

前序遍历(根→左→右)：先看清这棵树:根是 50,它的左孩子 30(下面挂着 20、40)、右孩子 80(下面挂着 70)。前序遍历从根 50 出发,一路「先根后左再右」地往下走。

前序遍历(根→左→右)：递归进入节点 值50(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值50 自己。

前序遍历(根→左→右)：把 值50 记进结果(它变绿),现在结果是 [50]。根记完了,接着先钻它的左子树。

前序遍历(根→左→右)：递归进入节点 值30(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值30 自己。

前序遍历(根→左→右)：把 值30 记进结果(它变绿),现在结果是 [50, 30]。根记完了,接着先钻它的左子树。

前序遍历(根→左→右)：递归进入节点 值20(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值20 自己。

前序遍历(根→左→右)：把 值20 记进结果(它变绿),现在结果是 [50, 30, 20]。根记完了,接着先钻它的左子树。

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

前序遍历(根→左→右)：值30 的左子树整段都走完了,递归回到 值30。前序里左边处理完,接下来轮到它的右子树。

前序遍历(根→左→右)：递归进入节点 值40(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值40 自己。

前序遍历(根→左→右)：把 值40 记进结果(它变绿),现在结果是 [50, 30, 20, 40]。根记完了,接着先钻它的左子树。

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

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

前序遍历(根→左→右)：值50 的左子树整段都走完了,递归回到 值50。前序里左边处理完,接下来轮到它的右子树。

前序遍历(根→左→右)：递归进入节点 值80(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值80 自己。

前序遍历(根→左→右)：把 值80 记进结果(它变绿),现在结果是 [50, 30, 20, 40, 80]。根记完了,接着先钻它的左子树。

前序遍历(根→左→右)：递归进入节点 值70(紫色)。前序的规矩是「根在最前」,所以一进来先轮到 值70 自己。

前序遍历(根→左→右)：把 值70 记进结果(它变绿),现在结果是 [50, 30, 20, 40, 80, 70]。根记完了,接着先钻它的左子树。

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

前序遍历(根→左→右)：值80 没有右孩子,右子树为空。到这儿,值80 的左、右子树都处理完了。

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

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

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

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

两个高频追问:显式栈迭代(先压右再压左);前中后序只差记录根的位置。