102.二叉树的层序遍历

题目:102.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

• 示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

• 示例 2：

输入：root = [1]
输出：[[1]]

• 示例 3：

输入：root = []
输出：[]

• 提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

思路

层序遍历（也称为广度优先遍历）是一种逐层访问二叉树节点的遍历方式。我们可以使用队列（FIFO）数据结构来实现它。

1. 首先检查根节点是否为空，如果为空，则返回空的结果列表。
2. 使用一个队列来存储节点。开始时将根节点放入队列中。
3. 当队列不为空时，遍历当前层的所有节点。对于每个节点，记录它的值，并将其左、右子节点放入队列中。
4. 将当前层的节点值列表加入结果集 result 中。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            // 将左右子节点加入队列
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        // 将当前层的节点值加入结果集
        result.add(level);
    }
    return result;
}