LeetCode 589. N 叉树的前序遍历
题目描述
题意分析
前序遍历先访问当前节点，再按孩子列表从左到右的顺序，完整遍历每棵子树。输入中的
null只是序列化时的分组标记，函数已经接收到节点及其孩子列表，不需要解析这些分隔符。题目进阶要求迭代实现。可以用显式栈保存下一步要处理的子树，模拟递归的访问顺序。
解法：迭代栈
核心思路
[!blue]
栈中的每个节点代表一棵尚未开始遍历的子树，栈顶代表下一棵要处理的子树。开始时只压入根；每次弹出节点，立即记录它的值，完成前序中的“先访问根”。
接下来要从左到右处理它的孩子，但栈是后进先出，所以必须把孩子从右到左压入。最左孩子最后入栈，会最先被弹出；它的后代又被压在右侧兄弟之上，因此这棵子树会被完整处理后，才轮到下一个兄弟。这就与递归前序的顺序一致。
每次用当前节点的孩子替换待处理的整棵子树后，栈仍按正确先后顺序保存剩余任务。树中每个非根节点只有一个父节点，只会被父节点压入一次，因此既不重复访问，也不需要额外的访问集合。栈为空时，全部子树已经处理完毕。
解题步骤
- 空树返回空结果，非空根入栈。
- 弹出节点并记录值。
- 逆序压入其孩子，循环直到栈空。
空树直接返回空结果。叶子没有孩子，记录值后不再压入节点；单节点树因而只执行一轮。孩子数量不固定，必须遍历完整列表。
代码实现
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
Node cur = stack.pop();
// 前序先访问当前子树的根
res.add(cur.val);
List<Node> children = cur.children;
if (children == null) {
continue;
}
// 逆序压栈，让最左子树先完整处理
for (int i = children.size() - 1; i >= 0; i--) {
stack.push(children.get(i));
}
}
return res;
}
}
func preorder(root *Node) []int {
res := make([]int, 0)
if root == nil {
return res
}
stack := []*Node{
root,
}
for len(stack) > 0 {
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 前序先访问当前子树的根
res = append(res, cur.Val)
children := cur.Children
// 逆序压栈，让最左子树先完整处理
for i := len(children) - 1; i >= 0; i-- {
stack = append(stack, children[i])
}
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点入栈、出栈各一次。
- 空间复杂度：$O(n)$，不计返回结果。显式栈保存的是待处理子树，并非单条递归路径；根含大量孩子时栈就能达到线性规模，单链时则只保留一个节点。
关键点总结
[!green]
- 弹出时访问根，逆序压入孩子，两个顺序共同实现前序。
- 新发现的后代位于已有兄弟之上，保证先完整处理当前子树。
易错点总结
[!yellow]
- 正序压入孩子，会先访问最右孩子。
- 使用队列，会改变子树优先的处理顺序。
- 压入孩子时就记录值，会把压栈顺序误当作前序顺序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 144. 二叉树的前序遍历 | 简单 | 前序先访问根再访问所有孩子，本题把二叉树固定左右孩子扩展成孩子列表。 |
| 590. N 叉树的后序遍历 | 简单 | 遍历结构相同，原题要在所有孩子处理完后才输出根。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！