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<Integer> rightSideView(TreeNode root) {
ArrayList<Integer> view = new ArrayList<Integer>();
if (root == null)
return view;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
while (!q.isEmpty()) {
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
TreeNode temp = q.poll();
if (i == 0)
view.add(temp.val);
if (temp.right != null)
q.offer(temp.right);
if (temp.left != null)
q.offer(temp.left);
}
}
return view;
}
}
My test result:
這道題目廉沮，沒(méi)做出來(lái)斟或。看了答案后，
感覺(jué)真的是少欺，算法是融入在血液的。刷題馋贤，培養(yǎng)的赞别，就是這么一種思想。
這種思想配乓，我在zigzag中也碰到過(guò)仿滔。
真的是，隨心所欲犹芹，不逾矩崎页。
想法在心中，題目在變腰埂，想法不會(huì)變飒焦。
而我現(xiàn)在是，題目不變屿笼，想法在不斷地變牺荠。無(wú)法找到準(zhǔn)確的方法來(lái)分析題目。
看到一道題目驴一，腦子還是一片空白休雌。
這道題目，我怎么就沒(méi)有想到肝断，拿隊(duì)列來(lái)做呢杈曲。然后采用zigzag的方式遍歷。
http://www.programcreek.com/2014/04/leetcode-binary-tree-right-side-view-java/
看了這篇博客就懂了胸懈。
**
總結(jié)： queue來(lái)遍歷tree
**
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<Integer> rightSideView(TreeNode root) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (root == null)
return ret;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode curr = q.poll();
if (i == 0) {
ret.add(curr.val);
}
if (curr.right != null)
q.offer(curr.right);
if (curr.left != null)
q.offer(curr.left);
}
}
return ret;
}
}
不難担扑。沒(méi)什么好總結(jié)的。
Anyway, Good luck, Richardo!
我用的還是老方法箫荡。沒(méi)什么好說(shuō)的魁亦。
然后網(wǎng)上看到別人用了這個(gè)方法，感覺(jué)挺巧妙的羔挡。
Their code:
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
rightView(root, result, 0);
return result;
}
public void rightView(TreeNode curr, List<Integer> result, int currDepth){
if(curr == null){
return;
}
if(currDepth == result.size()){
result.add(curr.val);
}
rightView(curr.right, result, currDepth + 1);
rightView(curr.left, result, currDepth + 1);
}
}
reference:
https://discuss.leetcode.com/topic/11768/my-simple-accepted-solution-java/2
感覺(jué)bfs 能做的洁奈，dfs都能做间唉，只是需要有個(gè)容器來(lái)暫存狀態(tài)。
Anyway,Good luck, Richardo! -- 09/07/2016
