题目描述

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

提示：

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

解题思路

对二叉树进行层序遍历即可，下一层的所有节点是当前层的所有左右子节点。用一个队列存储当前层的所有节点就好。

算法流程

1特例处理： 当根节点为空，则返回空列表 [] 。

2.初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] 。

3.BFS 循环： 当队列 queue 为空时跳出。
3.1新建一个临时列表 tmp ，用于存储当前层打印结果。
3.2当前层打印循环： 循环次数为当前层节点数（即队列 queue 长度）。

3.2.1出队： 队首元素出队，记为 node。
3.2.2打印： 将 node.val 添加至 tmp 尾部。
3.2.3添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue 。

3.3将当前层结果 tmp 添加入 res 。

4.返回值： 返回打印结果列表 res 即可。

代码解析

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {//存储当前层所有节点的队列Queue<TreeNode> queue = new LinkedList<>();//结果集List<List<Integer>> res = new ArrayList();//如果当前根节点不为空，则加入队列，开始执行流程if(root != null){queue.add(root);}//当队列非空（当前层数有节点没有执行深度优先遍历）时while(!queue.isEmpty()){//新建一个tmp队列List<Integer> tmp = new ArrayList();//执行循环//循环次数：每一层的节点的个数for(int i = queue.size(); i>0; i--){//队列弹出当前节点TreeNode currNode = queue.poll();//往队列中加入当前节点的左右子节点，构建下一层if(currNode.left != null){queue.add(currNode.left);}if(currNode.right != null){queue.add(currNode.right);}//临时队列中加入当前层的节点，构建当前层节点队列，加入结果集中tmp.add(currNode.val);}//加入结果集res.add(tmp);}//返回结果集return res;}
}