多叉树的递归/层序遍历

本文讲解的例题

LeetCode	力扣	难度
429. N-ary Tree Level Order Traversal	429. N 叉树的层序遍历	🟠
589. N-ary Tree Preorder Traversal	589. N 叉树的前序遍历	🟢
590. N-ary Tree Postorder Traversal	590. N 叉树的后序遍历	🟢

前置知识

阅读本文前，你需要先学习：

一句话总结

多叉树结构就是二叉树结构的延伸，二叉树是特殊的多叉树。

多叉树的遍历就是二叉树遍历的延伸。

森林是指多个多叉树的集合，单独一棵多叉树是一个特殊的森林。

二叉树的节点长这样，每个节点有两个子节点：

java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

cpp

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

javascript

var TreeNode = function(val) {
    this.val = val;
    this.left = null;
    this.right = null;
};

多叉树的节点长这样，每个节点有任意个子节点：

java

class Node {
    int val;
    List<Node> children;
}

cpp

class Node {
public:
    int val;
    vector<Node*> children;
};

python

class Node:
    def __init__(self, val: int):
        self.val = val
        self.children = []

type Node struct {
    val      int
    children []*Node
}

javascript

var Node = function(val) {
    this.val = val;
    this.children = [];
}

就这点区别，其他没了。

森林

这里介绍一下「森林」这个名词，后面讲到 Union Find 并查集算法时，会用到这个概念。

顾名思义，森林就是多个多叉树的集合（单独一棵多叉树也是一个特殊的森林），用代码表示就是多个多叉树的根节点列表，类似这样：

List<Node> forest;

只需对每个根节点分别进行 DFS/BFS 遍历，即可遍历森林的所有节点。

在并查集算法中，我们会同时持有多棵多叉树的根节点，那么这些根节点的集合就是一个森林。

接下来说下多叉树的遍历，和二叉树一样，也就递归遍历（DFS）和层序遍历（BFS）两种。