题目描述
思路解析
一句话答案：LeetCode 589 N 叉树的前序遍历：先记下当前节点的值，再用一个循环按从左到右递归走每个孩子，孩子个数不定就靠 children 列表接住，一趟走完就是前序，时间 O(n)。
N 叉树的前序遍历要返回什么
给一棵 N 叉树的根 root，把所有节点值按前序的顺序排成列表返回。N 叉树，也就是每个节点可以有任意多个孩子，孩子排成一个从左到右的有序列表，不像二叉树只固定左右两个。前序的规矩是：先记下当前节点的值，再按孩子列表从左到右，依次走完每个孩子的整棵子树。题面例子 root=[50,[30,[10,60]],20,80]，根 50 的孩子是 30、20、80，30 又带着 10 和 60，前序结果是 [50,30,10,60,20,80]。
孩子个数不定，二叉那套写法会漏掉
如果照二叉树前序的写法来套——访问根、递归左孩子、递归右孩子——到 N 叉树就卡住了：根 50 有三个孩子，你只写死了左右两个，第三个 80 会被整个漏掉。N 叉树的孩子个数事先不知道，可能一个也可能十个，不能靠固定几个变量接住。要改的只有一处：把「先左孩子再右孩子」换成「用一个循环，按顺序遍历 children 这个列表」，有几个孩子就走几个，一个不落。
先记自己，再挨个下钻孩子
递归写起来就三步：先把当前节点的值加进答案，再用循环按从左到右的顺序，对 children 里每个孩子递归做同一件事。下钻到某个孩子，它又先收自己、再走自己的孩子，规则层层套下去，直到某个节点没有孩子，循环空转、这一支自然收住。开头别忘判空：root 可能是空树，进来先看一眼，是空就返回空列表，否则对着空节点取 val 会报错。
题面这棵树，前序结果一步步拼出来
dfs(50)：记下 50，答案 [50]；50 的孩子是 30、20、80，先走 30。dfs(30)：记 30，答案 [50,30]；30 的孩子 10、60，先走 10。dfs(10)：记 10，答案 [50,30,10]，没孩子，返回。回 30 走 60：记 60，答案 [50,30,10,60]。30 的孩子走完，回 50 走第二个孩子 20：记 20，答案 [50,30,10,60,20]。最后第三个 80：记 80，答案排成 [50,30,10,60,20,80]，正是题面输出。
跑一遍是 O(n)，唯一的坑是把 N 叉当二叉
每个节点只被递归进入一次、记一次值，所有孩子指针合起来也只走一遍，n 个节点就是 O(n) 时间；空间看递归深度，树退化成一条链时栈深到 O(n)。边界也简单：空树直接返回空列表；只有一个根、没有孩子时返回它自己；根挂一排叶子时就是根，再从左到右逐个记下。这个坑就是只接了左右两个孩子，第三个起的全被静静漏掉。
面试追问不用递归，换一个显式栈
面试官若追问能不能不用递归，就换一个显式栈：根先入栈，再循环弹出栈顶、记下它的值，然后把它的孩子压回栈。这里有个反直觉的点——孩子要逆序压。栈是后进先出的，按 30、20、80 正序压，最后压进的 80 反而先出栈，前序顺序整个反掉；先压最右的 80、再 20、最后 30，栈顶才是最左的 30，弹出顺序才对得上从左到右。两种写法结果完全一样，只是把递归的调用栈换成了自己维护的栈。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住两句：前序是「先根、再从左到右走孩子」；用栈时孩子要逆序压，最左的才会最先出栈。
总览 · 这棵 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。一个栈、孩子逆序入栈，从头到尾只走一遍就拿到答案。
边界先想清：空树返回空；单节点返回自身；根带多个叶子时就是「根，再从左到右」。
面试重点：递归打底、迭代作进阶，并讲清逆序压栈的原因。
参考代码
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 preorder(self, root: 'Node') -> List[int]: ans = [] def dfs(node): if not node: return ans.append(node.val) for child in node.children: dfs(child) dfs(root) return ans复杂度
- 时间：O(n)，每个节点只被访问一次、记一次值；所有孩子指针总共也只遍历一遍，n 是节点总数
- 空间：O(n)，动画走的是迭代显式栈，根有大量孩子时一次就能压入 O(n) 个节点，所以是 O(n)；若改写成递归 DFS 则是栈深 O(h)、最坏仍 O(n)
易错点
面试追问把动画讲成自己的话
追问递归和迭代两种写法，面试该选哪个？
追问N 叉树和二叉树的前序，核心差别在哪？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
N 叉树的后序遍历
LeetCode 590 · 简单 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题