題目地址
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
題目要求
給你一個二叉樹氮昧，請你返回其按 層序遍歷 得到的節(jié)點值乳蛾。 （即逐層地揩慕，從左到右訪問所有節(jié)點）寝蹈。
示例 1:
二叉樹：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其層次遍歷結果：
[
[3],
[9,20],
[15,7]
]
解題思路
BFS問題，使用隊列逐層遍歷
需要注意的
- 根節(jié)點是
[]時未状，返回的不是null闰蚕，而是[]。 - 要使用
poll方法懂从。
思路
- 新建一個
List<List<Integer>>l來存放輸出結果授段，新建一個隊列用來存放每層的數(shù)據(jù)。 - 首先判斷根節(jié)點是否為空莫绣，如果不為空畴蒲，將根節(jié)點放入隊列，此時隊列size為
1对室。
判斷模燥。 - 判斷隊列是否為空，若不為空掩宜，獲取隊列size值
number蔫骂，循環(huán)number次，每次循環(huán)都會將隊列中的第x個元素（0<x<n+1)添加到一個List l2中牺汤，將第x個元素的左右節(jié)點添加到隊列中辽旋，循環(huán)結束后，將List l2添加到l中檐迟。繼續(xù)第三步操作补胚，直到隊列為空。 - 輸出l追迟。
代碼
/**
* 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的區(qū)別
為什么要使用poll方法操作隊列呢溶其？
共同點：
均返回隊列中第一個元素。
不同點：
poll：彈出第一個元素（返回并刪除）敦间，若為空瓶逃，返回null束铭。
peek：返回第一個元素（返回不刪除），若為空厢绝，返回null契沫。
element：返回第一個元素（返回不刪除），若為空昔汉，throw異常NoSuchElementException懈万。
