LeetCode 589. N 叉树的前序遍历

约 9 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节跳动
标签
深度优先搜索 树 栈
目录

题目描述

✅ 589. N 叉树的前序遍历

题意分析

给一棵 N 叉树的根节点，返回它的前序遍历值序列。这里的节点结构不再是 left / right 两个字段，而是一个 children 列表，孩子数量任意。前序的定义随之推广为：先访问根，再按 children 从左到右的顺序依次递归访问每一棵子树。

题面里的进阶要求是唯一的算法信号：「递归解法很简单，你可以使用迭代法完成此题吗？」。这句话把题目的重心从「会不会前序」挪到了「能不能手动模拟递归的调用栈」。递归版本三行就能写完，面试官问这题几乎必然是冲着迭代版去的，所以主解法应当直接给迭代写法。

约束方面：节点总数在 $0$ 到 $10^4$ 之间，树的高度不超过 $1000$。高度上限说明递归在这道题上不会真的爆栈，但也正因为它只有 $1000$，题目才敢说递归「很简单」——真正的考点不是性能而是对遍历机制的理解。

边界上要覆盖：根为空（返回空列表，不能返回 null）；只有一个根节点且没有孩子（children 可能是空列表，某些序列化实现下甚至是 null）；某个内部节点的 children 为空；孩子数量很多的扁平树（一个根挂 $10^4$ 个孩子，此时栈会瞬间涨到 $10^4$）。

解法：迭代栈

核心思路

递归版本的写法是「访问 root.val，然后对每个孩子递归」。它之所以正确，全靠函数调用栈帮我们记住了「当前节点还有哪些孩子没处理」。迭代版要做的事，就是把这个隐式栈搬到显式的数据结构里。

直接照搬会遇到一个麻烦：递归里每一层要记住「已经处理到第几个孩子」，如果显式栈里存 (节点, 孩子下标) 二元组，代码会变长很多。瓶颈在于我们误以为必须保留「进度」信息。

关键观察是：前序遍历的根节点在它整棵子树中排第一，而且访问完根之后，剩下的工作就是把若干棵子树按顺序依次做完整的前序遍历。也就是说，「待办事项」永远是一串互不嵌套、有先后顺序的子树，而不是「某个节点的第 k 个孩子」这种带进度的状态。既然待办项之间是纯粹的顺序关系，就可以一次性把某个节点的全部孩子都推进栈里，不需要记进度。

于是维护的不变量是：栈中自顶向下存放的节点，恰好是「所有还未被访问的子树的根」，且它们的出栈顺序就是这些子树在前序序列中应该出现的先后顺序。初始时栈里只有根，不变量显然成立。每次弹出栈顶 cur，把 cur.val 追加到结果，然后把 cur 的孩子全部压栈——由于栈是后进先出，要让最左边的孩子最先被弹出，压栈时必须从右往左（下标从 size - 1 递减到 $0$）。压完之后，栈顶依次是 cur 的第一个孩子、第二个孩子……再往下是 cur 原本的兄弟们，正好还原了前序应有的顺序，不变量得以保持。

这个「弹出即访问、逆序压孩子」的写法有一个额外好处：结果的追加时机与出栈时机完全对齐，不需要任何标记位或二次入栈。对比二叉树的后序遍历需要「访问标记」或者「先序反转」技巧，前序是所有遍历里最适合用朴素栈直接模拟的。

解题步骤

  • 先建结果列表，并对 root == null 立刻返回这个空列表而非 null。理由：题目要求返回集合类型，返回 null 会让调用方在遍历时崩溃；把判空写在最前面，后面所有代码都可以假定栈里的元素非空。

  • 建一个栈并把 root 压入。Java 用 ArrayDeque 而不是 Stack，理由：Stack 继承自 Vector，每个方法都带 synchronized，性能差且已被官方标记为遗留类；ArrayDeque 的 push / pop 都是 $O(1)$ 且无锁。Go 直接用切片模拟，append 入栈、切片截断出栈。

  • 主循环条件是「栈非空」。理由：栈为空等价于「没有未访问的子树」，此时前序序列已经完整，是唯一正确的终止条件。

  • 循环体第一步：弹出栈顶 cur，把 cur.val 追加进结果。理由：由不变量可知栈顶就是下一棵待访问子树的根，而前序中根排第一，所以出栈即访问，不需要延后。

  • 循环体第二步：取出 cur.children，若为 null 则跳过。理由：LeetCode 的 N 叉树在叶子节点上通常给空列表，但部分序列化实现会给 null；加一层判空成本极低，能挡住空指针。Go 里 nil 切片的 len 是 $0$，循环自然不执行，所以不用显式判。

  • 循环体第三步：用下标从 children.size() - 1 递减到 $0$，把孩子逐个压栈。理由：栈是后进先出，最后压入的最先弹出；要让第一个孩子最先被访问，它必须最后压入，所以遍历方向必须是从右往左。

  • 循环结束后返回结果列表。理由：不变量在循环退出时覆盖了整棵树，结果即为完整前序序列。

  • 以 root = [1, null, 3, 2, 4, null, 5, 6]（即根 1 有三个孩子 3、2、4，其中 3 又有两个孩子 5、6）走一遍。初始栈 [1]。第一轮弹出 1，结果 [1]，孩子是 [3, 2, 4]，从右往左压入 4、2、3，栈自底向上变成 [4, 2, 3]，栈顶是 3。第二轮弹出 3，结果 [1, 3]，孩子是 [5, 6]，从右往左压入 6、5，栈变成 [4, 2, 6, 5]，栈顶是 5。第三轮弹出 5，结果 [1, 3, 5]，无孩子。第四轮弹出 6，结果 [1, 3, 5, 6]，无孩子。第五轮弹出 2，结果 [1, 3, 5, 6, 2]。第六轮弹出 4，结果 [1, 3, 5, 6, 2, 4]，栈空退出。这与期望输出完全一致；注意第二轮压入 3 的孩子时，2 和 4 一直安静地待在栈底等待，正是不变量所说的「未访问子树按顺序排队」。

代码实现

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)$，其中 $n$ 是树的节点总数。每个节点恰好入栈一次、出栈一次，出栈时做一次常数时间的结果追加；所有节点的孩子数之和等于 $n - 1$（每条边贡献一次压栈），因此压栈操作总量也是 $O(n)$。
  • 空间复杂度：$O(n)$，栈的最大规模取决于树的形状。对于一个根挂着 $n - 1$ 个孩子的扁平树，第一轮就会把 $n - 1$ 个节点同时压入，达到 $O(n)$；对于一条链，栈中最多同时存 $O(h)$ 个节点。返回的结果列表本身是 $O(n)$，但它是答案不计入额外空间。

关键点总结

  • 迭代模拟递归的通用起手式是问一句：「递归调用栈里到底保存了什么信息？」。如果保存的只是一串顺序无关进度的待办任务（前序就是这种），朴素的节点栈就够了；如果必须记住「处理到第几个孩子」（比如后序、或者需要在孩子之间做事的场景），才要升级成存二元组或加访问标记。
  • 栈的后进先出与「从左到右」的语义天然相反，凡是要用栈保证左优先，压入时就必须逆序。这条规律在二叉树前序（先压右孩子再压左孩子）和 N 叉树前序（下标递减压入）里是同一件事。
  • 「出栈即访问」是前序遍历的专属红利，它让结果追加时机和栈操作完全同步。理解这一点，就能顺势推出 N 叉树后序的技巧：按正序压孩子做出栈访问，得到「根 → 右到左」的序列，最后整体反转即为后序。
  • 空返回值要给空集合而不是 null，children 也要防 null。这类接口契约上的细节在简单题里是主要的区分点。
  • 面试视角：字节考这题时，写完递归只是起点，真正的考察从「能不能改成迭代」开始。答题时最好主动说：「递归版三行，但调用栈是隐式的，我用显式栈重写一遍」，然后一边写一边点明「压栈要逆序，因为栈是 LIFO」。若被追问后序怎么办，直接给出「正序压孩子 + 结果反转」这个答案，能明显区分于死记模板的候选人。

易错点总结

  • 错误写法：压孩子时按下标从 $0$ 到 size - 1 正序压入 → 用例 根 1 带孩子 [3, 2, 4] → 最后压入的 4 最先出栈，结果变成 [1, 4, 2, 3]，孩子顺序整体反了。
  • 错误写法：root == null 时返回 null 而不是空列表 → 用例 root = [] → 判题方对返回值调用 size() 或做 for 遍历时抛空指针异常。
  • 错误写法：把「访问」写在入栈时而不是出栈时（压孩子的同时就把孩子的值追加进结果）→ 用例 根 1 带孩子 [3, 2, 4]，3 又带 [5, 6] → 结果变成 [1, 4, 2, 3, ...]，因为入栈顺序是逆序的，访问顺序也跟着反了。
  • 错误写法：Java 里用 Stack<Node> 并混用 push 与 add（Stack 继承自 Vector，add 是尾部追加而 pop 取的也是尾部，但 Stack.push 语义与 Deque.push 相反）→ 用例 任意多孩子的树 → 在把代码从 Stack 改写为 ArrayDeque 时忘记调整压入方向，输出顺序整体颠倒。
  • 错误写法：不判 cur.children == null 就直接调用 children.size() → 用例 序列化实现把叶子节点的 children 置为 null 的场景 → 访问第一个叶子时抛空指针异常。
  • 错误写法：Go 里出栈写成 cur := stack[0]; stack = stack[1:] → 用例 根 1 带孩子 [3, 2, 4]，3 带 [5, 6] → 这是队列的先进先出，得到的是层序遍历 [1, 3, 2, 4, 5, 6]，而正确前序是 [1, 3, 5, 6, 2, 4]。
  • 错误写法：循环条件写成 while (cur != null) 或用「栈非空且结果长度小于节点数」这类替代条件 → 用例 任意树 → 前者根本没用上栈的状态，遍历完第一条链就退出，漏掉大量节点。
  • 错误写法：为了「省一次判空」把根的入栈挪进循环里，写成先弹出再判 cur == null 就 continue，同时把所有孩子（包括可能为 null 的）都压栈 → 用例 含 null 占位孩子的输入 → 栈里混入空节点，虽然被 continue 挡住不至于崩，但栈规模无谓膨胀，且逻辑上模糊了「栈中都是待访问子树根」这条不变量，后续改成后序时必然出错。
  • 错误写法：结果用 LinkedList 并在每次访问时 addFirst → 用例 根 1 带孩子 [3, 2, 4] → 得到的是前序的逆序 [4, 2, 3, 1]，这个技巧属于后序遍历，用在前序上会整体反过来。
  • 错误写法：以为「N 叉树前序 = 逐层从左到右」，直接写 BFS → 用例 根 1 带孩子 [3, 2, 4]，3 带 [5, 6] → 输出 [1, 3, 2, 4, 5, 6]，这是层序不是前序，深度优先与广度优先在多叉树上差异极其明显。

相似题目

题目 难度 考察点
144. 二叉树的前序遍历 简单 孩子固定为两个，压栈时只需「先右后左」，是本题的特例
590. N 叉树的后序遍历 简单 出栈即访问的红利消失，需正序压孩子后把结果整体反转，或改用访问标记
94. 二叉树的中序遍历 简单 访问时机夹在左右子树之间，必须先沿左链一路压栈再弹出，不能一次性压完孩子
429. N 叉树的层序遍历 中等 把栈换成队列并按层切分，对比之下最能看清 LIFO 与 FIFO 的差别
559. N 叉树的最大深度 简单 遍历时还要携带深度信息，栈里要存二元组或改用带层计数的 BFS