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

N 叉树的前序遍历要返回什么

给一棵 N 叉树的根 root，把所有节点值按前序的顺序排成列表返回。N 叉树，也就是每个节点可以有任意多个孩子，孩子排成一个从左到右的有序列表，不像二叉树只固定左右两个。前序的规矩是：先记下当前节点的值，再按孩子列表从左到右，依次走完每个孩子的整棵子树。题面例子 root=[50,[30,[10,60]],20,80]，根 50 的孩子是 30、20、80，30 又带着 10 和 60，前序结果是 [50,30,10,60,20,80]。

孩子个数不定，二叉那套写法会漏掉

如果照二叉树前序的写法来套——访问根、递归左孩子、递归右孩子——到 N 叉树就卡住了：根 50 有三个孩子，你只写死了左右两个，第三个 80 会被整个漏掉。N 叉树的孩子个数事先不知道，可能一个也可能十个，不能靠固定几个变量接住。要改的只有一处：把「先左孩子再右孩子」换成「用一个循环，按顺序遍历 children 这个列表」，有几个孩子就走几个，一个不落。

先记自己，再挨个下钻孩子

递归写起来就三步：先把当前节点的值加进答案，再用循环按从左到右的顺序，对 children 里每个孩子递归做同一件事。下钻到某个孩子，它又先收自己、再走自己的孩子，规则层层套下去，直到某个节点没有孩子，循环空转、这一支自然收住。开头别忘判空：root 可能是空树，进来先看一眼，是空就返回空列表，否则对着空节点取 val 会报错。

题面这棵树，前序结果一步步拼出来

dfs(50)：记下 50，答案 [50]；50 的孩子是 30、20、80，先走 30。dfs(30)：记 30，答案 [50,30]；30 的孩子 10、60，先走 10。dfs(10)：记 10，答案 [50,30,10]，没孩子，返回。回 30 走 60：记 60，答案 [50,30,10,60]。30 的孩子走完，回 50 走第二个孩子 20：记 20，答案 [50,30,10,60,20]。最后第三个 80：记 80，答案排成 [50,30,10,60,20,80]，正是题面输出。

跑一遍是 O(n)，唯一的坑是把 N 叉当二叉

每个节点只被递归进入一次、记一次值，所有孩子指针合起来也只走一遍，n 个节点就是 O(n) 时间；空间看递归深度，树退化成一条链时栈深到 O(n)。边界也简单：空树直接返回空列表；只有一个根、没有孩子时返回它自己；根挂一排叶子时就是根，再从左到右逐个记下。这个坑就是只接了左右两个孩子，第三个起的全被静静漏掉。

面试追问不用递归，换一个显式栈

面试官若追问能不能不用递归，就换一个显式栈：根先入栈，再循环弹出栈顶、记下它的值，然后把它的孩子压回栈。这里有个反直觉的点——孩子要逆序压。栈是后进先出的，按 30、20、80 正序压，最后压进的 80 反而先出栈，前序顺序整个反掉；先压最右的 80、再 20、最后 30，栈顶才是最左的 30，弹出顺序才对得上从左到右。两种写法结果完全一样，只是把递归的调用栈换成了自己维护的栈。

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 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

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

};

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

}