LeetCode刷题之HOT100之二叉树的遍历

2024/6/14 这几天总是下雨，天气预报上面显示这个月都要持续下雨，下雨天了怎么办？我好想你，不敢打给你，我找不到原因。说着说着唱起来了哈哈！Anyway，昨天晚上打开了《涅朵奇卡一个女人的一生》，这本篇幅不长的小说我很久前就想看，还是从王小波那里知道的这本书，才开始看陀思妥耶夫斯基，看杜拉斯，茨威格等外国文学。那么接下来做个题放松一下吧。

1、题目描述

在这里插入图片描述

2、逻辑分析

题目要求对二叉树进行层序遍历，由于学过数据结构，对这些概念就较清晰。层序遍历抽象来说：就是把二叉树想象成蛋糕，一层一层的切下来。so，这题以什么算法来求解呢？与层序遍历结合的算法就是广度优先搜索（BFS），传统的BFS是一个节点一个节点的遍历，而这题可以在此基础上改进优化。比如示例1，首先我们设计一个队列。

初始：根节点进队列，此时队列里面只有3。
队列里面所有元素出队，即3出队，对3的左右子树遍历，此时[9，20]进队。
队列里面所有元素出队，即[9，20]出队，遍历左右子树，为[15，7]。

最后返回[[3]，[9，20]，[15，7]]。因为画图来说明会清晰，但是画图太麻烦了，遂不画了嘿嘿，代码展示。
有个题解讲的很清晰呀！图文并茂，比官方的好很多，放过来：层序遍历讲解。

3、代码演示

public List<List<Integer>> levelOrder(TreeNode root) {
        // 初始化一个二维列表来存储结果
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        // 如果根节点为空，则直接返回空的结果列表
        if(root == null){
            return res;
        }
        // 初始化一个队列，用于层序遍历 
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        // 将根节点加入队列
        queue.offer(root);
        // 当队列不为空时，继续遍历
        while(!queue.isEmpty()){
            // 初始化一个列表，用于存储当前层的节点值
            List<Integer> level = new ArrayList<Integer>();
            // 获取当前队列中的节点数，即当前层的节点数
            int curQueueLevel = queue.size();
            // 遍历当前层的所有节点
            for(int i = 0; i < curQueueLevel; 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);
                }
            }
            // 将当前层的节点值列表添加到结果列表中
            res.add(level);
        }
        // 返回结果列表 
       return res;
    }