![Upload Paste_Image.png failed. Please try again.]
My code:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null)
return result;
Queue<TreeNode> q = new LinkedList<TreeNode>();
Queue<TreeNode> qSon = new LinkedList<TreeNode>();
q.add(root);
ArrayList<Integer> sample = new ArrayList<Integer>();
while(!q.isEmpty()) {
TreeNode temp = q.poll();
sample.add(temp.val);
if (q.isEmpty()) {
if (temp.left != null)
qSon.add(temp.left);
if (temp.right != null)
qSon.add(temp.right);
result.add(sample);
sample = new ArrayList<Integer>();
q = qSon;
qSon = new LinkedList<TreeNode>();
}
else {
if (temp.left != null)
qSon.add(temp.left);
if (temp.right != null)
qSon.add(temp.right);
}
}
return result;
}
}
My test result:
這道題目還可以镀赌，有一點(diǎn)小難度。主要就是，二叉樹如果層級遍歷痴怨。
level traversal
那么就是新建一個queue，然后把子孫往里面放就行了搅窿。然后就能遍歷节值。
但是這道題目不是遍歷，而是把一層層的東西存入List即碗。
那么就有個問題焰情，如果有一個queue，無法體現(xiàn)出層與層之間的界限剥懒。所以内舟，我用了兩個queue。
一個用來存放這一層的樹結(jié)點(diǎn)初橘，然后一個個存入 List中验游。一個用來存放下一層的子結(jié)點(diǎn)，然后當(dāng)上一層q空時保檐，代表上一層遍歷已經(jīng)結(jié)束了耕蝉。然后立馬讓上一層的queue指向下一層，下一層的queue則立馬重新申請一塊內(nèi)存夜只。以此循環(huán)垒在。
差不多就這樣吧。
PS: 剛剛聽了同學(xué)的思路扔亥，感覺更好场躯，只需要使用一個queue。設(shè)置一個level size砸王。
import java.util.*;
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> output = new ArrayList<List<Integer>>();
if (root == null)
return output;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> list = new ArrayList<Integer>();
for(int i = 0; i < levelSize; i++) {
TreeNode n = queue.poll();
list.add(n.val);
if(n.left != null)
queue.add(n.left);
if(n.right != null)
queue.add(n.right);
}
output.add(list);
}
return output;
}
}
更加簡潔推盛！
**
總結(jié)：Queue， level traversal
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null)
return ret;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
while (!q.isEmpty()) {
int levelSize = q.size();
ArrayList<Integer> group = new ArrayList<Integer>();
for (int i = 0; i < levelSize; i++) {
TreeNode temp = q.poll();
group.add(temp.val);
if (temp.left != null)
q.offer(temp.left);
if (temp.right != null)
q.offer(temp.right);
}
ret.add(group);
}
return ret;
}
}
簡單題目谦铃。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
list.add(node.val);
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
ret.add(list);
}
return ret;
}
}
簡單題耘成。做完今天十道題目的任務(wù)就完成了。
Anyway, Good luck, Richardo! -- 08/29/2016
沒想到還有一種 recursion的方法：
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}
helper(root, 0, ret);
return ret;
}
private void helper(TreeNode root, int level, List<List<Integer>> ret) {
if (root == null) {
return;
}
if (level > ret.size() - 1) {
ret.add(new ArrayList<Integer>());
}
ret.get(level).add(root.val);
helper(root.left, level + 1, ret);
helper(root.right, level + 1, ret);
}
}
也很簡潔。
這讓我想起了一道題目瘪菌。
就是樹節(jié)點(diǎn)還有第三個指針next撒会，把左邊的鏈接到右邊。
也是可以用recursion做的师妙。
iteration就是dfs诵肛，因?yàn)閱栴}就是要我們解決每一層的關(guān)系，所以BFS是最直接的想法默穴。
dfs的話怔檩，如果原來的狀態(tài)都保存在那里，等到下一次再次回到這一層的時候蓄诽，就可以繼續(xù)用了薛训。
也就是說，即使下去了下仑氛，再回來乙埃，一切都還未變，該怎樣還可以怎樣锯岖。
這兩道題目都是這個特征介袜。
Anyway, Good luck,Richardo! -- 09/06/2016
