LeetCode 102. 二叉树的层序遍历 (Java)
题目地址
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
题目要求
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例 1:
二叉树：[3,9,20,null,null,15,7],
1 | 3 |
返回其层次遍历结果：
1 | [ |
解题思路
BFS问题，使用队列逐层遍历
需要注意的
- 新建一个
List<List<Integer>>l来存放输出结果，新建一个队列用来存放每层的数据。 - 首先判断根节点是否为空，如果不为空，将根节点放入队列，此时队列size为
1。
判断。 - 判断队列是否为空，若不为空，获取队列size值
number，循环number次，每次循环都会将队列中的第x个元素（0<x<n+1)添加到一个List l2中，将第x个元素的左右节点添加到队列中，循环结束后，将List l2添加到l中。继续第三步操作，直到队列为空。 - 输出l。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> l=new ArrayList<>();
Queue<TreeNode> q=new LinkedList<TreeNode>();
if(root!=null){
q.add(root);
}
while(!q.isEmpty()){
List<Integer> l2=new ArrayList<>();
int number=q.size();
while(number>0){
TreeNode t=q.poll();
l2.add(t.val);
if(t.left!=null){
q.add(t.left);
}
if(t.right!=null){
q.add(t.right);
}
number--;
}
l.add(l2);
}
return l;
}
}队列中poll,peek和element的区别
为什么要使用poll方法操作队列呢？
共同点：
均返回队列中第一个元素。
不同点：poll：弹出第一个元素（返回并删除），若为空，返回null。peek：返回第一个元素（返回不删除），若为空，返回null。element：返回第一个元素（返回不删除），若为空，throw异常NoSuchElementException。
