多叉树的递归/层序遍历

一句话总结
多叉树结构就是 二叉树结构 的延伸，二叉树是特殊的多叉树。森林是指多个多叉树的集合。
多叉树的遍历就是 二叉树遍历 的延伸。
二叉树的节点长这样，每个节点有两个子节点：
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));
    }
}

}