Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
題意：按層遍歷一個(gè)二叉樹后輸出遍歷結(jié)果影所。
思路：
這是一道典型的寬度優(yōu)先搜索的題目，學(xué)會(huì)一個(gè)套路很容易掌握這類問題的解決方法。
核心是用隊(duì)列签赃，先把搜索的起點(diǎn)加入隊(duì)列违崇，然后開始重復(fù)這樣一個(gè)步驟：1凫岖、從隊(duì)列頭部取出元素娶视；2叮喳、看從這個(gè)元素能搜索到的鄰接的元素库车，把它們加入到隊(duì)列中巨柒；3、直到隊(duì)列為空柠衍，證明已經(jīng)搜索完了全部的元素洋满。
這道題需要按層搜索，所以有一個(gè)關(guān)鍵點(diǎn)：不能每次從隊(duì)列取出一個(gè)元素珍坊，而是一次取出一層的元素牺勾。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();//當(dāng)前層有的元素個(gè)數(shù)
List<Integer> list = new ArrayList<>();
for (int i = 0; i < size; i++) {//只遍歷當(dāng)前層的元素
TreeNode cur = q.poll();
list.add(cur.val);
//把下層元素加到隊(duì)列中
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
res.add(list);
}
return res;
}