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

这道题到底在问什么

输入

root = [1,null,3,2,4,null,5,6]

输出

[5,6,3,2,4,1]

最优解：一步一步想明白

1. 3记住「先遍历孩子列表、最后收根」这一条,下面每一帧都在套它。
2. 4后序序列还是空的开局后序序列为空。DFS 从根节点 50 出发,口诀是先把孩子走完再收自己,我们一路往下探。
3. 5先处理 50 的孩子走到节点 50(紫色)。它的孩子列表是 30、80,按后序规矩,要先把这些孩子从左到右一个个递归走完,50 自己留到最后再收。
4. 6先处理 30 的孩子走到节点 30(紫色)。它的孩子列表是 10、20,按后序规矩,要先把这些孩子从左到右一个个递归走完,30 自己留到最后再收。
5. 7先处理 10 的孩子走到节点 10(紫色)。它的孩子列表是 15、25,按后序规矩,要先把这些孩子从左到右一个个递归走完,10 自己留到最后再收。
6. 815 没有孩子走到节点 15(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
7. 915 入列,后序 +1叶子 15 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15。
8. 1025 没有孩子走到节点 25(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
9. 1125 入列,后序 +1叶子 25 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15 25。
10. 1210 入列,后序 +110 的孩子 15、25 都已经收完了,现在轮到 10 自己。把 10 追加进后序序列(变绿),目前序列是 15 25 10。
11. 1320 没有孩子走到节点 20(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
12. 1420 入列,后序 +1叶子 20 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15 25 10 20。
13. 1530 入列,后序 +130 的孩子 10、20 都已经收完了,现在轮到 30 自己。把 30 追加进后序序列(变绿),目前序列是 15 25 10 20 30。
14. 16先处理 80 的孩子走到节点 80(紫色)。它的孩子列表是 70、90,按后序规矩,要先把这些孩子从左到右一个个递归走完,80 自己留到最后再收。
15. 17先处理 70 的孩子走到节点 70(紫色)。它的孩子列表是 75、78,按后序规矩,要先把这些孩子从左到右一个个递归走完,70 自己留到最后再收。
16. 1875 没有孩子走到节点 75(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
17. 1975 入列,后序 +1叶子 75 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15 25 10 20 30 75。
18. 2078 没有孩子走到节点 78(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
19. 2178 入列,后序 +1叶子 78 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15 25 10 20 30 75 78。
20. 2270 入列,后序 +170 的孩子 75、78 都已经收完了,现在轮到 70 自己。把 70 追加进后序序列(变绿),目前序列是 15 25 10 20 30 75 78 70。
21. 2390 没有孩子走到节点 90(紫色)。它的孩子列表是空的,是个叶子,没有可往下走的孩子,马上就能收它。
22. 2490 入列,后序 +1叶子 90 没有孩子要等,直接把它追加进后序序列(变绿),目前序列是 15 25 10 20 30 75 78 70 90。
23. 2580 入列,后序 +180 的孩子 70、90 都已经收完了,现在轮到 80 自己。把 80 追加进后序序列(变绿),目前序列是 15 25 10 20 30 75 78 70 90 80。
24. 2650 入列,后序 +150 的孩子 30、80 都已经收完了,现在轮到 50 自己。把 50 追加进后序序列(变绿),目前序列是 15 25 10 20 30 75 78 70 90 80 50。
25. 27答案 = [15, 25, 10, 20, 30, 75, 78, 70, 90, 80, 50]整棵树走完,所有节点都收进了后序序列:15 25 10 20 30 75 78 70 90 80 50。可以看到每个节点都在自己的孩子全部收完之后才入列,根 50 排在最后,这就是后序的特征。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }

};

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);
    }

}

复杂度

面试官可能追问