102 二叉树的层序遍历

一、题目

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

二、题解

思路：利用队列实现 BFS

队列具有“先进先出”的特性。当我们把根节点放入队列后，每次从队列里拿出一个节点，就把它的值记录下来，顺便把它的左子节点和右子节点（如果不为空）按顺序排到队列的末尾去。

但这道题有一个小难点：它要求我们把结果按照层级分组（返回 List<List<Integer>>），而不是平铺成一个一维数组。

如何区分哪几个节点属于同一层？ 关键技巧在于：在进入每一层的 while 循环时，提前记录当前队列的大小 (size)。这个 size 就是当前这一层包含的节点个数。我们只需要写一个内部的 for 循环，循环 size 次，就能精准地把当前层的所有节点处理完，然后再把它们打包成一个小列表存入最终结果中。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        // 如果根节点为空，直接返回空列表
        if (root == null) {
            return result;
        }

        // 使用 LinkedList 实现队列来存储节点
        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 currentNode = queue.poll();
                currentLevel.add(currentNode.val);

                // 如果左子节点不为空，加入队列（为下一层做准备）
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                // 如果右子节点不为空，加入队列
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            // 当前层遍历完毕，将小列表加入最终结果
            result.add(currentLevel);
        }

        return result;
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

评论