【数据结构与算法 | 队列篇】力扣102, 107-1. 力扣102 : 二叉树的层序遍历
最编程
2024-06-03 06:55:37
...
(1). 题
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1] 输出:[[1]]
示例 3:
输入:root = [] 输出:[]
提示:
- 树中节点数目在范围
[0, 2000]
内 -1000 <= Node.val <= 1000
(2). 思路
由题,可知方法返回一个集合,该集合的元素仍然是一个集合. 该题需要用到队列数据结构.如果二叉树是空树,直接返回空集合. 如果不是,则将根节点入队.由于根节点在队列中,将size初始化为1,n的作用则是用于更新size.while循环,只要队列不为空,那么就new一个集合,for循环依次出队,并将出队的节点的值add到集合中收集起来,如果其有左孩子或右孩子,则将该孩子节点入队,并将n++. 一次循环结束时,将小集合add入大集合中.
(3). 解
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> bl = new ArrayList<>();
Deque<TreeNode> deque = new LinkedList<>();
if(root == null) {
return bl;
}
deque.offer(root);
int size = 1;
int n = 0;
//只要队列不为空
while(!deque.isEmpty()) {
List<Integer> l = new ArrayList<>();
for(int i =0 ; i < size; i++) {
TreeNode tn = deque.poll();
l.add(tn.val);
if(tn.left != null) {
deque.offer(tn.left);
n++;
}
if(tn.right != null) {
deque.offer(tn.right);
n++;
}
}
size = n;
n = 0;
bl.add(l);
}
return bl;
}
}
上一篇: 数控机床面板刻字说明