LeetCode 590. N 叉树的后序遍历

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 拼多多
标签
深度优先搜索 树 栈

题目描述

✅ 590. N 叉树的后序遍历

image-20260929102001632

image-20260929102001765

题意分析

返回 N 叉树的后序遍历：按 children 中给定的顺序，依次输出每棵孩子子树的后序结果，最后输出当前节点。一个节点可以有任意多个孩子，不能只处理前两个。

题面用 null 分隔输入中的孩子分组，那是序列化格式；接口接收的已经是树节点，可以直接遍历 children。空树返回空列表，进阶要求用迭代代替递归。

解法：递归 DFS

核心思路

[!blue]
dfs(node, res) 的含义是把当前子树的完整后序序列追加到 res 末尾。遇到空节点直接结束；非空节点先按原顺序递归每个孩子，等这些调用全部返回后，再追加当前节点值。

每个孩子的递归都会完整输出它的子树，因此依次调用后，各子树既保持输入顺序，也都位于父节点之前，正好满足后序定义。叶子没有孩子，循环直接结束，随后输出自身。

所有递归共享同一个结果列表，每个节点只追加一次；无需逐层创建子列表再复制合并。递归栈保存尚未完成的父节点，负责在孩子处理完后回到正确的位置。

解题步骤

  1. 创建本次调用的结果列表。
  2. 递归入口为空则返回。
  3. 按原顺序遍历全部孩子。
  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)$，每个节点和孩子关系处理一次。
  • 空间复杂度：辅助栈 $O(h)$，结果另占 $O(n)$。

关键点总结

[!green]

  • 追加时机决定后序，必须在全部孩子之后。
  • 孩子之间保持输入顺序。
  • 每次调用使用新的结果容器。

解法二：栈遍历后反转

核心思路

[!blue]

把后序的“各孩子从左到右，最后根节点”整体反过来，会得到“先根节点，再按从右到左的顺序处理孩子子树，子树内部也反向”。先用栈生成这个反向序列，最后统一反转即可。

每次弹出节点就先记录它，再按 children 的原顺序把孩子入栈。栈后进先出，所以右边的孩子先被处理；它新加入的后代又位于栈顶，因此会先完成整棵子树，再处理左边的兄弟。最终反转时，父子顺序和兄弟顺序都会恢复成后序要求。

解题步骤

  1. 空树直接返回空列表，否则把根节点入栈。
  2. 弹出栈顶，记录节点值，再将全部孩子按原顺序入栈。
  3. 重复直到栈空，此时每个节点都已经记录一次。
  4. 反转结果列表，得到按原孩子顺序排列的后序遍历。

代码实现

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

        if (root == null) {
            return res;
        }

        Deque<Node> stack = new ArrayDeque<>();

        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();

            res.add(node.val);
            for (Node child : node.children) {
                stack.push(child);
            }
        }

        Collections.reverse(res);

        return res;
    }
}

func postorder(root *Node) []int {
    res := make([]int, 0)
    if root == nil {
        return res
    }

    stack := []*Node{
        root,
    }
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        for _, child := range node.Children {
            stack = append(stack, child)
        }
    }

    for left, right := 0, len(res)-1; left < right; left, right = left+1, right-1 {
        res[left], res[right] = res[right], res[left]
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点入栈、出栈和记录一次，最后反转也只需线性时间。
  • 空间复杂度：辅助栈最坏为 $O(n)$，一个节点可能一次压入很多孩子；结果另占 $O(n)$。

关键点总结

[!green]

  • 孩子按原顺序入栈，弹出时才会从右到左处理。
  • 中间序列是反向后序，最后的整体反转不能省略。

易错点总结

[!yellow]

  • 先追加自己再递归：变成前序。
  • 逆序遍历孩子：子树之间顺序反转。
  • 只处理前两个孩子：丢失 N 叉节点的其他分支。
  • 每层返回并复制整个子列表：链状树可能产生平方量级复制。

相似题目

题目 难度 关联与区别
145. 二叉树的后序遍历 简单 后序访问时机相同，本题要等待可变数量的孩子都结束。
589. N 叉树的前序遍历 简单 原题先输出根，本题最后输出根，显式栈模拟时需相应保存访问阶段。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/61739036
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！