多叉树的递归/层序遍历

多叉树的递归/层序遍历

本文讲解的例题

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

python

javascript

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

java

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

cpp

python

javascript

就这点区别，其他没了。

森林

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

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

List<Node> forest;

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

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

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