一句话总结
多叉树结构就是 二叉树结构 的延伸，二叉树是特殊的多叉树。森林是指多个多叉树的集合。
多叉树的遍历就是 二叉树遍历 的延伸。
二叉树的节点长这样，每个节点有两个子节点：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
}
多叉树的节点长这样，每个节点有任意个子节点：
class Node {
int val;
List children;
}
就这点区别，其他没了。
递归遍历（DFS）
对比二叉树的遍历框架看多叉树的遍历框架吧：
// 二叉树的遍历框架
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置
traverse(root.left);
// 中序位置
traverse(root.right);
// 后序位置
}
// N 叉树的遍历框架
void traverse(Node root) {
if (root == null) {
return;
}
// 前序位置
for (Node child : root.children) {
traverse(child);
}
// 后序位置
}
唯一的区别是，多叉树没有了中序位置，因为可能有多个节点嘛，所谓的中序位置也就没什么意义了。
层序遍历（BFS）
多叉树的层序遍历和 二叉树的层序遍历 一样，都是用队列来实现，无非就是把二叉树的左右子节点换成了多叉树的所有子节点。所以多叉树的层序遍历也有三种写法，下面一一列举。
写法一
第一种层序遍历写法：
void levelOrderTraverse(Node root) {
if (root == null) {
return;
}
Queue q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
Node cur = q.poll();
// 访问 cur 节点
System.out.println(cur.val);
// 把 cur 的所有子节点加入队列
for (Node child : cur.children) {
q.offer(child);
}
}
}
写法二
第二种能够记录节点深度的层序遍历写法：
void levelOrderTraverse(Node root) {
if (root == null) {
return;
}
Queue q = new LinkedList<>();
q.offer(root);
// 记录当前遍历到的层数（根节点视为第 1 层）
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
// 访问 cur 节点，同时知道它所在的层数
System.out.println("depth = " + depth + ", val = " + cur.val);
for (Node child : cur.children) {
q.offer(child);
}
}
depth++;
}
}
写法三
第三种能够适配不同权重边的写法：
class State {
Node node;
int depth;
public State(Node node, int depth) {
this.node = node;
this.depth = depth;
}
}
void levelOrderTraverse(Node root) {
if (root == null) {
return;
}
Queue q = new LinkedList<>();
// 记录当前遍历到的层数（根节点视为第 1 层）
q.offer(new State(root, 1));
while (!q.isEmpty()) {
State state = q.poll();
Node cur = state.node;
int depth = state.depth;
// 访问 cur 节点，同时知道它所在的层数
System.out.println("depth = " + depth + ", val = " + cur.val);
for (Node child : cur.children) {
q.offer(new State(child, depth + 1));
}
}
}
