LeetCode 590. N 叉树的后序遍历

2022-10-09 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 590. N 叉树的后序遍历

题意分析

给一棵 N 叉树的根节点，按后序遍历的顺序返回所有节点值组成的列表。N 叉树的节点结构是 val 加一个 children 列表，孩子的个数不固定。

后序遍历的定义只有一句话：先按顺序遍历完全部子树，最后访问自己。对二叉树来说是「左 → 右 → 根」，推广到 N 叉树就是「孩子 1 → 孩子 2 → … → 孩子 k → 根」。孩子之间必须严格按 children 列表给出的顺序，不能重排。

从这个定义能直接读出两个性质。第一，根节点必然是输出序列的最后一个元素——因为它要等所有子树都处理完才轮到自己。第二，每棵子树的输出是结果序列中一段连续的区间，并且这些区间按孩子顺序依次排列。这两点是检查实现是否正确的最快判据。

题目本身没有任何优化空间：每个节点必须访问且只需访问一次，答案长度就是节点数，所以 $O(n)$ 时间是下界也是上界。真正需要拿捏的是访问时机——「什么时候把 val 写进结果」这一个动作放在循环之前还是之后，决定了前序还是后序，没有第三种可能。这也是这类题在面试中的全部考点：能不能把遍历的结构和访问时机分离着讲清楚。

约束里节点总数是线性规模，但树的高度可能退化成链（每个节点只有一个孩子），递归深度随之达到节点数量级，这一点在讨论空间复杂度时必须提到。

边界：根为空时返回空列表而不是报错；某个节点的 children 为空列表（叶子）时循环一次都不进，直接输出自己；children 里理论上不该有空指针，但递归入口保留空判可以让代码对不规范输入也安全。

解法：递归 DFS

核心思路

后序遍历的定义本身就是递归的：一棵树的后序序列 = 各棵子树的后序序列按顺序拼接 + 根节点值。既然定义是递归的，直接照着定义写递归就是最短路径，不需要任何转化。

于是递归函数的契约定成：dfs(node) 的职责是「把以 node 为根的整棵子树的后序序列，按顺序追加到结果列表末尾」。这个契约有两个要点。其一，它是「追加」而不是「返回」——用一个在所有递归层之间共享的结果列表，让每层直接往末尾写，避免了每层构造并合并子列表带来的 $O(n^2)$ 拷贝。其二，它承诺只追加、不修改已有内容，所以各层写入的区间天然不会互相干扰，拼接顺序完全由调用顺序决定。

有了这个契约，函数体就只剩三行：空节点直接返回（空子树的后序序列是空的，什么都不用追加）；依次对每个孩子递归（按 children 的顺序调用，于是各子树的区间按孩子顺序排好）；最后追加自己的 val。

最后那一行的位置就是全部的算法内容。放在循环之后是后序，放在循环之前就变成了前序（589 题），中间没有任何别的差别。理解「遍历的骨架相同，只有访问时机不同」这一点，前序、后序两道题就合并成了一道。至于中序，在 N 叉树上没有定义——因为孩子多于两个时，「中间」的位置不唯一。

不变量：每次 dfs(node) 返回时，结果列表相比调用前恰好多了一段内容，它正是以 node 为根的子树的完整后序序列。用归纳法看：叶子节点显然成立（只追加自己）；对内部节点，若所有孩子都满足这个不变量，则循环结束时列表末尾依次是各子树的后序序列，再追加根值，正好构成本子树的后序序列。

递归没有重复子问题、也没有可剪枝的分支，每个节点恰好被调用一次，所以复杂度就是 $O(n)$，无法再优化。唯一的代价是调用栈，深度等于树高。

值得一提的是迭代写法的思路（面试常见追问）：用栈做前序遍历，但孩子按逆序入栈得到「根 → 孩子 k → … → 孩子 1」的序列，再把整个结果反转，就得到后序。它避免了栈深度限制，但可读性不如递归，通常作为补充方案给出。

解题步骤

在入口创建结果列表，调用递归函数，最后返回该列表。为什么：把「准备容器」和「填充容器」分成两层，递归函数就可以保持无返回值的纯追加语义；结果列表由所有递归层共享，避免每层构造子列表再合并——那样每个节点会被复制 $O(h)$ 次，总代价退化到 $O(nh)$。

递归函数第一行判 node == null 直接返回。为什么：空子树的后序序列是空的，按契约什么都不该追加，直接返回正好；这一行同时兜住了「根为空」这个入口边界和「children 里意外含空指针」这种不规范输入，一处判断覆盖两种场景。

按 children 列表的原始顺序，依次对每个孩子递归调用。为什么：后序要求子树之间保持给定顺序，而每次递归调用都会在结果末尾追加一段连续区间，所以调用顺序直接决定了区间顺序——顺序遍历 children 就等于让区间按孩子顺序排列。这里不需要判断孩子个数，children 为空时循环一次都不进，叶子节点自然落入主逻辑。

循环结束之后，才把 node.val 追加到结果末尾。为什么：这一行的位置就是「后序」的全部含义——必须等所有子树的区间都写完，根节点才排在它们之后。把它移到循环之前，输出立刻变成前序；这是本题唯一需要精确控制的地方。

返回结果列表。

以一棵具体的树走一遍。设根为 1，它有三个孩子依次是 3、2、4；其中 3 又有两个孩子 5、6；其余节点都是叶子。（这正是 LeetCode 该题的示例，期望输出 [5, 6, 3, 2, 4, 1]。）

dfs(1)：非空，进入循环。

先处理第一个孩子 dfs(3)：非空，进入它自己的循环。先 dfs(5)——5 是叶子，children 为空、循环不进，直接追加 5，结果变成 [5]，返回。再 dfs(6)——同理追加 6，结果变成 [5, 6]，返回。3 的循环结束，现在才追加 3，结果变成 [5, 6, 3]，返回。注意此刻结果末尾的这三个元素 [5, 6, 3] 恰好是以 3 为根的子树的完整后序序列，且 3 排在它两个孩子之后——不变量成立。

回到 dfs(1) 的循环，处理第二个孩子 dfs(2)：叶子，追加 2，结果 [5, 6, 3, 2]。

处理第三个孩子 dfs(4)：叶子，追加 4，结果 [5, 6, 3, 2, 4]。

1 的循环结束，最后追加根值 1，结果 [5, 6, 3, 2, 4, 1]，与期望一致。

从这条轨迹能看出两处校验点：根节点 1 确实落在最末尾；三棵子树分别占据 [5, 6, 3]、[2]、[4] 三段连续区间，且按 children 顺序排列。如果把追加根值那一行挪到循环之前，同一棵树会输出 [1, 3, 5, 6, 2, 4]——那是前序，根跑到了最前面，每棵子树的区间虽然仍然连续，但根节点插在了自己的子树之前。

代码实现

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        dfs590(root, res);
        return res;
    }

    // 契约：把以 node 为根的整棵子树的后序序列追加到 res 末尾。
    private void dfs590(Node node, List<Integer> res) {
        if (node == null) {
            return;
        }
        // 按 children 的原始顺序递归，各子树的区间随之按序排列。
        for (Node child : node.children) {
            dfs590(child, res);
        }
        // 这一行放在循环之后即后序；挪到循环之前就变成前序。
        res.add(node.val);
    }
}

func postorder(root *Node) []int {
    res := make([]int, 0)
    // 契约：把以 node 为根的整棵子树的后序序列追加到 res 末尾。
    var dfs func(node *Node)
    dfs = func(node *Node) {
        if node == nil {
            return
        }
        // 按 Children 的原始顺序递归，各子树的区间随之按序排列。
        for _, child := range node.Children {
            dfs(child)
        }
        // 这一行放在循环之后即后序；挪到循环之前就变成前序。
        res = append(res, node.Val)
    }
    dfs(root)
    return res
}

复杂度分析

时间复杂度：$O(n)$，n 为节点总数。凭什么：每个节点恰好被 dfs 调用一次，函数体内除了遍历自己的 children 之外只有一次列表追加；而所有节点的孩子数之和等于边数 n - 1，因此循环的总执行次数是线性的。列表追加是均摊 $O(1)$，不影响总量。这也是理论下界——输出本身就有 n 个元素。

空间复杂度：$O(h)$ 辅助空间，h 为树高，最坏 $O(n)$。凭什么：唯一的额外开销是递归调用栈，深度等于当前路径长度即树高；每层栈帧只存节点指针和循环变量，是常数。树退化成一条链（每个节点只有一个孩子）时 h = n，这也是递归写法在极深树上有栈溢出风险的原因。结果列表占 $O(n)$，但那是必须的输出，通常不计入辅助空间。

关键点总结

树的三种深度优先遍历共用同一套骨架，唯一的差别是「访问当前节点」这一行放在哪里：放在递归子树之前是前序，放在之后是后序。把这句话记牢，589 与 590 就是同一道题。

N 叉树没有中序遍历。孩子超过两个时「中间」的位置不唯一，这是 N 叉树相比二叉树少一种遍历方式的根本原因，面试中被追问时能一句话答出来是个小加分。

递归函数要么「返回子结果由上层合并」，要么「共享一个容器直接追加」。后者省掉了每层的列表构造与拷贝，把 $O(nh)$ 降到 $O(n)$——凡是收集型的递归都应优先用共享容器。

写递归前先把契约说清楚：「调用这个函数会对结果产生什么效果」。本题的契约是「把本子树的后序序列追加到末尾」，有了它，正确性可以直接用归纳法一句话说完。

空间复杂度要说成 $O(h)$ 而不是笼统的 $O(n)$，并主动指出「链状树时 h = n」。能区分「典型情况」与「最坏情况」是评价复杂度分析是否到位的常见标准。

面试延伸：被问「不用递归怎么写」时，标准答案是用栈做「根 → 孩子逆序」的前序遍历，最后把结果整体反转。理由是后序序列的逆序恰好是「根 → 最后一个孩子 → … → 第一个孩子」这种变形前序，而前序用栈很容易写。若被要求「不许反转」，则需要在栈里额外记录每个节点已处理到第几个孩子，模拟真正的后序回溯。

易错点总结

把 res.add(node.val) 写在孩子循环之前：示例树 1 → [3 → [5, 6], 2, 4] → 输出 [1, 3, 5, 6, 2, 4]，这是前序结果，而正确答案是 [5, 6, 3, 2, 4, 1]。

逆序遍历 children：同一棵树 → 输出 [4, 2, 6, 5, 3, 1]，子树之间的顺序被翻转；后序只要求「根在最后」，孩子之间必须保持原顺序。

每层递归都新建列表再合并返回：一条长度为 n 的链状树 → 每个节点的结果被向上复制 $O(n)$ 次，总代价 $O(n^2)$，节点数上万时超时。

忘记 node == null 判断：root 为空 → 直接访问 node.children 抛空指针异常，而正确行为是返回空列表。

在循环里判断 child != null 却漏了入口判空：postorder(null) → 仍然在第一行就崩溃；判空应放在递归入口，一处覆盖所有情形。

把 children 当成二叉树的 left / right 只处理前两个孩子：示例树的根有三个孩子 → 第三个孩子 4 被完全忽略，输出缺项。

递归时传错节点（如仍传 node 而不是 child）：任意有孩子的树 → 无限递归，栈溢出。

用一个成员变量存结果却不在入口重置：判题连续调用两次 postorder → 第二次的结果拼在第一次后面，长度翻倍。

用「前序 + 反转」的迭代思路时，孩子按正序入栈：栈的后进先出会让最后一个孩子先出栈，得到的是「根 → 孩子 1 → … → 孩子 k」，反转后孩子顺序整体颠倒；必须逆序入栈才对。

迭代写法忘记最后反转结果：得到的是「根 → 孩子 k → … → 孩子 1」这种变形前序 → 示例树输出 [1, 4, 2, 3, 6, 5]，恰好是正确答案的逆序。

相似题目

题目	难度	考察点
589. N 叉树的前序遍历	简单	与本题骨架完全相同，只把访问根的那一行移到孩子循环之前
145. 二叉树的后序遍历	简单	孩子退化成固定的左右两个，迭代写法可用「上一个访问节点」判断是否回溯
144. 二叉树的前序遍历	简单	二叉树版前序，迭代实现最简单，只需右孩子先入栈
94. 二叉树的中序遍历	简单	只有二叉树才有中序，迭代要「一路向左压栈再出栈转右」，与本题结构不同
429. N 叉树的层序遍历	中等	改为广度优先，用队列按层展开并记录每层大小，输出的是二维列表
559. N 叉树的最大深度	简单	同为后序框架，但每层向上返回的是子树深度的最大值而非追加序列
428. 序列化和反序列化 N 叉树	困难	遍历时还要写出孩子个数或分隔符，才能让序列反过来唯一确定树结构
102. 二叉树的层序遍历	中等	429 的二叉树版本，可用来对照「孩子数固定」与「孩子数不定」的写法差异