102. 二叉树的层序遍历
LeetCode题目要求
给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例
![图](/i/l/?n=23&i=blog/458364/202301/458364-20230120174810393-1084213789.png)
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
解题思路
层序遍历,就是从上至下,一层层的遍历下来;按要求是每层从左到右输出元素,那么可以使用队列的方式。如根节点 3 入队,出队就是一个结果;9,20 在第二次入队,9 20 在出队,他们都符合队列先进先出的特性。
上代码
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> q = new LinkedList<>();
// 根元素入队
q.offer(root);
// 遍历出队
while (!q.isEmpty()) {
// 队列不为空时,此时让队列元素出队,但要注意此时队列的 size,因为后面我们还要入队子节点
int size = q.size();
// 用于存储每层的结果
List<Integer> levelRes = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode curr = q.poll();
levelRes.add(curr.val);
if (curr.left != null) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
}
res.add(levelRes);
}
return res;
}
}
附:学习资料链接
标签:遍历,curr,层序,Day15,入队,二叉树,null,root From: https://www.cnblogs.com/blacksonny/p/17062977.html