N 叉树的后序遍历 图解题解

后序遍历要返回一串什么样的顺序

给一棵 N 叉树的根节点 root，把所有节点的值按后序排成一个列表返回。N 叉树就是每个节点的孩子不止两个，而是存在一个孩子列表里，从左到右排好。题面示例 root=[1,null,3,2,4,null,5,6]，画出来是根 1 底下挂着 3、2、4 三个孩子，3 又带着 5、6，最后要返回 [5,6,3,2,4,1]。

先收根、再走孩子，序列会歪成什么样

不少人第一笔就把根 1 写进结果，再去处理孩子——这样收出来的是 [1,3,5,6,2,4]，根跑到了最前头，正是前序而不是后序。后序的定义卡得很死：一个节点的值，必须等它名下所有孩子、连同孩子的孩子都进了结果，才轮得到它自己。收根的时机差一步，整串顺序就全歪了。

孩子全收完，才轮到收自己

把这条规矩摊开来看：站在任意一个节点上，先别急着收自己，而是照孩子列表从左到右，一个个钻下去递归。等某个孩子是叶子、底下再没有孩子了，它就能直接进结果；要等这个节点名下的孩子全部落进结果，才排得上收它自己的值。二叉树的后序是先左右两个孩子再收自己，N 叉树只是把『两个孩子』换成『一整个孩子列表』，规矩一模一样。

一个 dfs 在每个节点做的三件事

写成递归就是一个 dfs(node)：先判空，node 为空直接返回，空树和走到底都靠它兜住；再用 for 循环，按顺序对 node.children 里的每个孩子递归调用 dfs；等这个 for 循环整个跑完、所有孩子都收完了，才把 node.val 追加进答案数组 ans。这三步的先后不能乱——append 自己这一步，永远排在 for 循环之后。

拿 [1,null,3,2,4,null,5,6] 从头收到尾

从根 1 进 dfs。1 的孩子是 3、2、4，先钻第一个孩子 3。3 的孩子是 5、6，又先钻 5：5 没有孩子，直接进结果，ans=[5]；回到 3 收第二个孩子 6，6 也没孩子，ans=[5,6]；3 的孩子收完，收 3 自己，ans=[5,6,3]。回到 1 的第二个孩子 2，没孩子，ans=[5,6,3,2]；第三个孩子 4，没孩子，ans=[5,6,3,2,4]；1 的三个孩子全收完，最后收根 1，ans=[5,6,3,2,4,1]，和题面输出一致。

先把根收了，后序当场变前序

最爱出岔子的是收根的时机：把 append 自己写在 for 循环前头，根提前入了列，后序当场退化成前序。孩子顺序也不能乱，从右往左递归会让同层孩子的相对次序整个颠倒。还有空节点，忘了判空、遇到空树就直接越界报错。复杂度这边倒是干净：每个节点只被处理一回，时间 O(n)；额外开销是递归栈，深度等于当前走到的层数，最多就是树高 h，空间 O(h)，最坏树退化成一条链时 h=n。

Python

from typing import List
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        ans = []
        def dfs(node):
            if not node:
                return
            for child in node.children:
                dfs(child)
            ans.append(node.val)
        dfs(root)
        return ans

C++

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) { val = _val; }
    Node(int _val, vector<Node*> _children) { val = _val; children = _children; }
};
class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> ans;
        function<void(Node*)> dfs = [&](Node* node) {
            if (!node) return;
            for (Node* child : node->children) dfs(child);
            ans.push_back(node->val);
        };
        dfs(root);
        return ans;
    }

};

Java

import java.util.*;
class Node {
    public int val;
    public List<Node> children;
    public Node() { children = new ArrayList<>(); }
    public Node(int _val) { val = _val; children = new ArrayList<>(); }
    public Node(int _val, List<Node> _children) { val = _val; children = _children; }
}
class Solution {
    public List<Integer> postorder(Node root) {
        ArrayList<Integer> ans = new ArrayList<>();
        dfs(root, ans);
        return ans;
    }
    private void dfs(Node node, List<Integer> ans) {
        if (node == null) return;
        for (Node child : node.children) dfs(child, ans);
        ans.add(node.val);
    }

}