429.N叉树的层序遍历

难度：中等

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间

广度优先搜索法（BFS）

这道题和 102 题基本一样，改动在于在每一层的遍历过程中，一个节点有多个子节点，获取子节点的方式需要稍作改动。

层序遍历一个二叉树。就是从左到右、一层一层地去遍历二叉树。这种遍历的方式需要借用一个辅助数据结构即队列来实现。

队列具有 先进先出 的特性，符合层序遍历的逻辑。这种层序遍历的方式就是图论中的广度优先遍历，只不过我们应用在了二叉树上。

算法流程：

处理特例：若根节点为空，则返回空列表
根节点入队
BFS 循环：判断队列是否为空。如果不为空，说明还有节点需要遍历
1. 初始化当前层的节点个数 currentLevelSize 为队列的大小。
2. 首先初始化一个空的列表 currentLevelList 用于存储当前层的节点值。
3. 使用一个内层循环，遍历当前层的节点。循环次数为当前层的节点个数 currentLevelSize。
  1. 从队列中取出一个节点 current，将其值添加到 currentLevelList 中。
  2. 如果当前节点有子节点，将子节点入队。
4. 将存储当前层节点值的列表 currentLevelList 添加到结果列表 result 中。
5. 此时队列中已经把当前层的节点都出队了，同时把下一层的节点都入队了，因此队列大小刚好变成了下一层的节点个数。
返回结果列表

代码展示

java

public List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> result = new ArrayList<>();
    // 若根节点为空，则返回空列表
    if (root == null) {
        return result;
    }
    Deque<Node> queue = new LinkedList<>();
    // 根节点入队
    queue.add(root);
    // BFS 循环
    while (!queue.isEmpty()) {
        int currentLayerSize = queue.size();
        List<Integer> currentLayerList = new ArrayList<>();
        // 这里一定要使用固定大小currentLayerSize，不要使用queue.size()，因为queue不停地出队入队，所以其大小是不断变化的
        for (int i = 0; i < currentLayerSize; i++) {
            Node current = queue.poll();
            currentLayerList.add(current.val);
            if (current.children != null) {
                queue.addAll(current.children);
            }
        }
        result.add(currentLayerList);
    }
    return result;
}

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

时间复杂度：O(n)，其中 n 是 N 叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，最差情况下，根节点有 n-1 个子节点。

总结

二叉树的层序遍历模板需要记住。

429.N叉树的层序遍历 ​

广度优先搜索法（BFS） ​

代码展示 ​

总结 ​

429.N叉树的层序遍历

广度优先搜索法（BFS）

代码展示

总结