102. 层序遍历#

public List<List<Integer>> levelOrder(TreeNode root) {
    // 最终结果：按层存储每层节点值
    List<List<Integer>> result = new ArrayList<>();

    // 从根节点（第 0 层）开始递归收集
    traverseLevel(root, 0, result);

    // 返回层序遍历结果
    return result;
}

private void traverseLevel(TreeNode node, int level, List<List<Integer>> result) {
    // 递归终止条件：空节点不处理
    if (node == null) return;

    // 如果当前层的容器还不存在，先创建这一层的列表
    if (level >= result.size()) {
        result.add(new ArrayList<>());
    }

    // 把当前节点值加入它所属的层
    result.get(level).add(node.val);

    // 递归处理左子树，层号 +1
    traverseLevel(node.left, level + 1, result);
    // 递归处理右子树，层号 +1
    traverseLevel(node.right, level + 1, result);
}

public List<List<Integer>> levelOrder(TreeNode root) {
    // 保存最终答案：每层一个列表
    List<List<Integer>> result = new ArrayList<>();

    // 边界处理：空树直接返回空结果
    if (root == null) return result;

    // 队列用于 BFS（先进先出，天然按层推进）
    Queue<TreeNode> queue = new LinkedList<>();
    // 根节点先入队
    queue.offer(root);

    // 队列不空表示仍有节点待访问
    while (!queue.isEmpty()) {
        // 固定当前层节点数量，避免与下一层混杂
        int levelSize = queue.size();
        // 存放当前层所有节点值
        List<Integer> currentLevel = new ArrayList<>();

        // 依次处理当前层节点
        for (int i = 0; i < levelSize; i++) {
            // 取出一个当前层节点
            TreeNode node = queue.poll();
            // 记录该节点值到当前层结果
            currentLevel.add(node.val);

            // 左孩子存在就入队，留到下一层处理
            if (node.left != null) queue.offer(node.left);
            // 右孩子存在就入队，留到下一层处理
            if (node.right != null) queue.offer(node.right);
        }

        // 当前层处理完毕，加入总结果
        result.add(currentLevel);
    }

    // 返回层序遍历结果
    return result;
}