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;
}
以上代码注释清晰，作题还是得多练啊，练着练着就知道怎么做了。
4、复杂度分析
- 时间复杂度：O(n)。这里我们实际也是对每个节点都遍历访问了，故时间复杂度是O(n)。
- 空间复杂度：O(n)。最差情况下，即当树为平衡二叉树时，最多有 n/2个树节点同时在 队列中，使用 O(n) 大小的额外空间。
over,写完啦！真的很耗时间啊，刷leetcode，慢慢来吧
less is more.