760 · Binary Tree Right Side View - LintCode

# Description

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom

Example

Example 1

Input: {1,2,3,#,5,#,4}
Output: [1,3,4]
Explanation:
   1            
 /   \
2     3         
 \     \
  5     4

Example 2

Input: {1,2,3}
Output: [1,3]
Explanation:
   1            
 /   \
2     3

# BFS Solution

這題可以用 dfs,bfs
最先是想到用 BFS，分層看這個問題。 (有點像這題：Binary Tree Level Order Traversal )
基本上是要樹最右邊的 node, 如果右邊是空但左邊有的話，才把左邊的加進去 queue 裡。
也就是說要是沒有右邊 node 才加左邊的～

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/

	public class Solution {
	/**
	* @param root: the root of the given tree
	* @return: the values of the nodes you can see ordered from top to bottom
	*/
	public List<Integer> rightSideView(TreeNode root) {
	List<Integer> res = new ArrayList<>();
	if (root == null) return res;

	Queue<TreeNode> queue = new LinkedList<>();
	queue.offer(root);

	while (!queue.isEmpty()){
	// 不是一次一個 node, 是一次好幾個 node,
	// 所要用 size, 有 size 就要 loop 看看
	int size = queue.size();
	TreeNode node = null;
	for (int i = 0; i < size; i++){
	node = queue.poll();
	// 一定先放左子樹
	if (node.left != null){
	queue.offer(node.left);
	}
	// 第二個放右邊的
	if (node.right != null){
	queue.offer(node.right);
	}
	}
	// 當 loop 結束時，就是 queue 裡最後一個
	//Queue 最後一個是右邊 node, 此時把它加進去。
	res.add(node.val);

	}

	return res;
	}
	}