package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**199. Binary Tree Right Side View

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.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4]. */

public class _199 {
	//Using BFS is pretty straightforward. But there might be a smarter way.
	public List<Integer> rightSideView(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();
		if(root == null) return res;
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		q.offer(root);
		while(!q.isEmpty()){
			int currentSize = q.size();
			int i = 0;
			TreeNode currentNode = null;
			for(; i < currentSize; i++){
				currentNode = q.poll();
				if(currentNode.left != null) q.offer(currentNode.left);
				if(currentNode.right != null) q.offer(currentNode.right);
			}
			res.add(currentNode.val);
		}
		return res;
	}
	
	public static void main(String...strings){
		_199 test = new _199();
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.right = new TreeNode(5);
		root.right.right = new TreeNode(4);
		List<Integer> result = test.rightSideView(root);
		for(int i : result){
			System.out.print(i + ", ");
		}
	}
}

@@ -573,81 +573,8 @@
  %7B%0D%0A
-%09//Using BFS is pretty straightforward. But there might be a smarter way.
 %0D%0A%09p
@@ -644,16 +644,19 @@
 ger%3E res
+ult
  = new A
@@ -664,23 +664,16 @@
 rayList%3C
-Integer
 %3E();%0D%0A%09%09
@@ -674,16 +674,17 @@
 );%0D%0A%09%09if
+ 
 (root ==
@@ -696,24 +696,27 @@
 ) return res
+ult
 ;%0D%0A%09%09Queue%3CT
@@ -743,24 +743,16 @@
 kedList%3C
-TreeNode
 %3E();%0D%0A%09%09
@@ -774,16 +774,17 @@
 %0A%09%09while
+ 
 (!q.isEm
@@ -789,16 +789,17 @@
 Empty())
+ 
 %7B%0D%0A%09%09%09in
@@ -800,24 +800,17 @@
 %0A%09%09%09int 
-currentS
+s
 ize = q.
@@ -817,24 +817,29 @@
 size();%0D%0A%09%09%09
+for (
 int i = 0;%0D%0A
@@ -836,18 +836,36 @@
 t i = 0;
+ i %3C size; i++) %7B
 %0D%0A
+%09
 %09%09%09TreeN
@@ -876,105 +876,93 @@
 curr
-entNode = null
+ = q.poll()
 ;%0D%0A%09%09%09
+%09
-for(; i %3C currentSize; i++)%7B%0D%0A%09%09%09%09currentNode = q.poll(
+if (i == size-1) %7B%0D%0A%09%09%09%09%09result.add(curr.val
 );%0D%0A
+%09%09%09%09%7D%0D%0A
 %09%09%09%09if
+ 
 (curr
-entNode
 .lef
@@ -964,32 +964,40 @@
 r.left != null) 
+%7B%0D%0A%09%09%09%09%09
 q.offer(currentN
@@ -992,23 +992,16 @@
 fer(curr
-entNode
 .left);%0D
@@ -1005,26 +1005,27 @@
 );%0D%0A
+%09%09%09%09%7D%0D%0A
 %09%09%09%09if
+ 
 (curr
-entNode
 .rig
@@ -1036,16 +1036,24 @@
 = null) 
+%7B%0D%0A%09%09%09%09%09
 q.offer(
@@ -1056,23 +1056,16 @@
 fer(curr
-entNode
 .right);
@@ -1073,39 +1073,16 @@
 %0A%09%09%09
+%09
 %7D%0D%0A%09%09%09
-res.add(currentNode.val);
+%7D
 %0D%0A%09%09
@@ -1096,16 +1096,19 @@
 turn res
+ult
 ;%0D%0A%09%7D%0D%0A%09

edit 199