N 叉树的前序遍历

记住两句：前序是「先根、再从左到右走孩子」；用栈时孩子要逆序压，最左的才会最先出栈。

总览 · 这棵 N 叉树：先看清这棵 N 叉树。根是 50，它有三个孩子，从左到右排成一个列表 30、20、80；30 自己又带两个孩子 10 和 60，其余都是叶子。N 叉树的「N」意思是一个节点的孩子个数不固定，孩子是一串有先后的列表。前序遍历的规矩很简单：先访问根，再按从左到右的顺序，挨个把每个孩子的整棵子树走一遍。这棵树的前序结果会是 50、30、10、60、20、80，下面用一个栈一步步把它演出来。

入栈 · 根 50 进栈：迭代法用一个栈来模拟递归。开局把根 50 压进栈，结果序列还是空。盯住右边两块面板：上面是栈，栈顶在最上面、下一个出栈；下面是已访问、记进答案的结果序列。接下来只重复一个动作：弹出栈顶、访问它、再把它的孩子逆序压回栈。

看栈顶 · 50：栈里现在只有 50，它就是栈顶。前序第一步永远是访问根，所以下一帧把它弹出来访问。

弹出并访问 · 50：弹出栈顶 50，访问它，把 50 记进结果序列。结果序列现在是 50。访问完一个节点，紧接着要安排它的孩子。

孩子逆序入栈 · 50：50 访问完，把它的三个孩子 30、20、80 压回栈。这里有个关键：要逆序压，先压最右的 80、再压 20、最后压最左的 30。这样栈顶就是最左的孩子 30，保证后面从左到右访问，符合前序要求。

看栈顶 · 30：现在栈顶是最左的孩子 30。后面 20、80 在它下面排队等着，先把 30 这一整支彻底走完，再轮到它们。

弹出并访问 · 30：弹出 30 并访问，结果序列变成 50、30。30 自己还带着孩子，继续安排它的孩子。

孩子逆序入栈 · 30：30 有两个孩子 10 和 60，同样逆序压栈：先压 60、再压 10，于是栈顶变成最左的 10。注意此刻栈里从顶到底是 10、60、20、80，正好等着按这个顺序处理。

看栈顶 · 10：栈顶是 10，它是 30 的第一个孩子。

弹出并访问 · 10：弹出 10 访问，结果序列接到 50、30、10。

叶子结算 · 10：10 是叶子，没有孩子可压栈，它这一支到此为止，直接处理完，节点变绿。

看栈顶 · 60：栈顶轮到 60，它是 30 的第二个孩子。

弹出并访问 · 60：弹出 60 访问，结果序列添到 60。到这里，30 的两个孩子 10、60 都访问完了。

叶子结算 · 60：60 也是叶子，无孩子，处理完。30 这一整棵子树就彻底走完了，接下来回到根 50 剩下的孩子。

看栈顶 · 20：栈顶现在是 20，它是根 50 的第二个孩子，刚才一直在栈底耐心等着。

弹出并访问 · 20：弹出 20 访问，结果序列添到 20。

叶子结算 · 20：20 没有孩子，处理完，节点变绿。栈里只剩根的最后一个孩子 80 了。

看栈顶 · 80：栈里只剩 80，它是根 50 的最后一个孩子。

弹出并访问 · 80：弹出 80 访问，结果序列添到 80。这时栈空了。

叶子结算 · 80：80 是叶子，处理完。栈已经清空，整趟遍历到此结束。

完成 · 前序序列：所有节点都访问过了。看结果序列：50、30、10、60、20、80。它正好印证前序的规矩：先根 50，再把第一个孩子 30 的整棵子树走完（30、10、60），然后第二个孩子 20，最后第三个孩子 80。一个栈、孩子逆序入栈，从头到尾只走一遍就拿到答案。

边界先想清：空树返回空；单节点返回自身；根带多个叶子时就是「根，再从左到右」。

面试重点：递归打底、迭代作进阶，并讲清逆序压栈的原因。