102. 二叉树层次顺序遍历
小白渣翻译
给定二叉树的 root ，返回其节点值的层序遍历。 （即从左到右，逐级）。
例子
小白教室做题
在大学某个自习的下午，小白坐在教室看到这道题。想想自己曾经和白月光做题，现在大过年的，也是只有自己练题了。真是若对黄花孤负酒，怕黄花，也笑人岑寂。
这时候黑长直女神过来问：小白，你复习到二叉树了吗，这道题你有什么思路啊？
小白内心镇定：这机会不就来了吗，小美，《热辣滚烫》有机会一起去看看吧？
哦，不是，题目描述意思说的简单一些。
这种题目我们首先把他进行下条件梳理
- 树类的题目，我们首先要对树结构和BFS（广度优先搜索），DFS（深度优先搜索）有一定了解哈。
- 另外，熟悉了算法后，我们对于Queue（队列）也要相对熟悉下，这样能更加方便的解题。
那么，对于这道题来说，Binary Tree Level Order Traversal，也就是二叉树的层序遍历，顾名思义，就是按照从上到下、从左到右的顺序遍历二叉树中的所有节点。我们可以使用广度优先搜索（BFS）算法来实现层序遍历。
其中，BFS算法的基本思路是：
1.将根节点加入队列中。
2.循环执行以下操作，直到队列为空：
- 从队列中取出一个节点
- 将该节点的值加入到结果列表中
- 将该节点的左右子节点（如果存在）加入到队列中
小美：小伙子，可以啊，这不仅逻辑感人，阅读理解也有俩下子！不过电影票要你买单哦。
小白：没问题，谁叫为了“真爱”呢。
真正面试环节
面试官：你可以解答这道”二叉树层级循序遍历“的题目吗，来看看你对树结构的理解。
小白：嘿嘿，这不巧了么这不是。
public List<List<Integer>> levelOrder(TreeNode root) {
// 定义一个 List<List<Integer>> 类型的结果列表 result，用于存储层序遍历的结果。
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
// 创建一个队列 queue，用于存储待遍历的节点。
Queue<TreeNode> queue = new LinkedList<>();
// 将根节点 root 加入到队列 queue 中。
queue.offer(root);
// 循环执行以下操作，直到队列 queue 为空：
// 从队列 queue 中取出一个节点 node
// 将节点 node 的值加入到结果列表 result 中
// 将节点 node 的左右子节点（如果存在）加入到队列 queue 中
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
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;
}
小明：OK，完事儿，等着面试官来表扬自己吧。他肯定会说：小子，你是个好手！工位都给你准备好了，工资你说了算。
面试官：矮油，不错啊，不过你这能不能写个测试啊。
小明OS：今年这个找工市场，人言洛阳花似锦，偏我来时不逢春。。。不是，怎么还让我些test case 啊！
public static void main(String[] args) {
// 创建二叉树
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
// 创建BinaryTreeLevelOrderTraversal对象并调用levelOrder
BinaryTreeLevelOrderTraversal solution = new BinaryTreeLevelOrderTraversal();
List<List<Integer>> traversalResult = solution.levelOrder(root);
// 输出结果
System.out.println(traversalResult);
}
小白：您好，面试官，这回可以了吧，我终于有钱请小美看电影了！
============================================================================
🍀🍀🍀🍀🍀🍀更多算法题解请看 面试数据结构与算法总结分类+leetcode目录【基础版】
编码道路漫漫，只要先看脚下的路，徐徐前进即可。