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

这道题到底在问什么

输入

root=[50,[30,[10,60]],20,80]（根 50 的孩子是 30、20、80；30 的孩子是 10、60）

输出

[50,30,10,60,20,80]

先想最直接的笨办法

先看清这棵 N 叉树。根是 50，它有三个孩子，从左到右排成一个列表 30、20、80；30 自己又带两个孩子 10 和 60，其余都是叶子。N 叉树的「N」意思是一个节点的孩子个数不固定，孩子是一串有先后的列表。前序遍历的规矩很简单：先访问根，再按从左到右的顺序，挨个把每个孩子的整棵子树走一遍。这棵树的前序结果会是 50、30、10、60、20、80，下面用一个栈一步步把它演出来。（动画第 4 步）

最优解：一步一步想明白

1. 3记住两句：前序是「先根、再从左到右走孩子」；用栈时孩子要逆序压，最左的才会最先出栈。
2. 4目标：求前序序列先看清这棵 N 叉树。根是 50，它有三个孩子，从左到右排成一个列表 30、20、80；30 自己又带两个孩子 10 和 60，其余都是叶子。N 叉树的「N」意思是一个节点的孩子个数不固定，孩子是一串有先后的列表。前序遍历的规矩很简单：先访问根，再按从左到右的顺序，挨个把每个孩子的整棵子树走一遍。这棵树的前序结果会是 50、30、10、60、20、80，下面用一个栈一步步把它演出来。
3. 5栈：50迭代法用一个栈来模拟递归。开局把根 50 压进栈，结果序列还是空。盯住右边两块面板：上面是栈，栈顶在最上面、下一个出栈；下面是已访问、记进答案的结果序列。接下来只重复一个动作：弹出栈顶、访问它、再把它的孩子逆序压回栈。
4. 6栈顶 = 50栈里现在只有 50，它就是栈顶。前序第一步永远是访问根，所以下一帧把它弹出来访问。
5. 7结果：50弹出栈顶 50，访问它，把 50 记进结果序列。结果序列现在是 50。访问完一个节点，紧接着要安排它的孩子。
6. 8栈顶 = 3050 访问完，把它的三个孩子 30、20、80 压回栈。这里有个关键：要逆序压，先压最右的 80、再压 20、最后压最左的 30。这样栈顶就是最左的孩子 30，保证后面从左到右访问，符合前序要求。
7. 9栈顶 = 30现在栈顶是最左的孩子 30。后面 20、80 在它下面排队等着，先把 30 这一整支彻底走完，再轮到它们。
8. 10结果：50、30弹出 30 并访问，结果序列变成 50、30。30 自己还带着孩子，继续安排它的孩子。
9. 11栈顶 = 1030 有两个孩子 10 和 60，同样逆序压栈：先压 60、再压 10，于是栈顶变成最左的 10。注意此刻栈里从顶到底是 10、60、20、80，正好等着按这个顺序处理。
10. 12栈顶 = 10栈顶是 10，它是 30 的第一个孩子。
11. 13结果：50、30、10弹出 10 访问，结果序列接到 50、30、10。
12. 1410 处理完10 是叶子，没有孩子可压栈，它这一支到此为止，直接处理完，节点变绿。
13. 15栈顶 = 60栈顶轮到 60，它是 30 的第二个孩子。
14. 16结果：50、30、10、60弹出 60 访问，结果序列添到 60。到这里，30 的两个孩子 10、60 都访问完了。
15. 1760 处理完60 也是叶子，无孩子，处理完。30 这一整棵子树就彻底走完了，接下来回到根 50 剩下的孩子。
16. 18栈顶 = 20栈顶现在是 20，它是根 50 的第二个孩子，刚才一直在栈底耐心等着。
17. 19结果：50、30、10、60、20弹出 20 访问，结果序列添到 20。
18. 2020 处理完20 没有孩子，处理完，节点变绿。栈里只剩根的最后一个孩子 80 了。
19. 21栈顶 = 80栈里只剩 80，它是根 50 的最后一个孩子。
20. 22结果：50、30、10、60、20、80弹出 80 访问，结果序列添到 80。这时栈空了。
21. 2380 处理完80 是叶子，处理完。栈已经清空，整趟遍历到此结束。
22. 24答案：50、30、10、60、20、80所有节点都访问过了。看结果序列：50、30、10、60、20、80。它正好印证前序的规矩：先根 50，再把第一个孩子 30 的整棵子树走完（30、10、60），然后第二个孩子 20，最后第三个孩子 80。一个栈、孩子逆序入栈，从头到尾只走一遍就拿到答案。

⚠️ 容易写错的地方

完整代码（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 preorder(self, root: 'Node') -> List[int]:
        ans = []
        def dfs(node):
            if not node:
                return
            ans.append(node.val)
            for child in node.children:
                dfs(child)
        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> preorder(Node* root) {
        vector<int> ans;
        function<void(Node*)> dfs = [&](Node* node) {
            if (!node) return;
            ans.push_back(node->val);
            for (Node* child : node->children) dfs(child);
        };
        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> preorder(Node root) {
        ArrayList<Integer> ans = new ArrayList<>();
        dfs(root, ans);
        return ans;
    }
    private void dfs(Node node, List<Integer> ans) {
        if (node == null) return;
        ans.add(node.val);
        for (Node child : node.children) dfs(child, ans);
    }

}

复杂度

面试官可能追问