77import java .util .List ;
88import java .util .Queue ;
99
10- /**199. Binary Tree Right Side View
11-
12- 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.
13-
14- For example:
15- Given the following binary tree,
16-
17- 1 <---
18- / \
19- 2 3 <---
20- \ \
21- 5 4 <---
22-
23- You should return [1, 3, 4]. */
24-
2510public class _199 {
2611
27- public static class Solution1 {
28- /**credit: https://leetcode.com/problems/binary-tree-right-side-view/discuss/56012/My-simple-accepted-solution(JAVA)*/
29- public List <Integer >rightSideView (TreeNode root ) {
30- List <Integer >result =new ArrayList <>();
31- rightView (root ,result ,0 );
32- return result ;
33- }
12+ public static class Solution1 {
13+ /**
14+ * credit: https://leetcode.com/problems/binary-tree-right-side-view/discuss/56012/My-simple-accepted-solution(JAVA)
15+ */
16+ public List <Integer >rightSideView (TreeNode root ) {
17+ List <Integer >result =new ArrayList <>();
18+ rightView (root ,result ,0 );
19+ return result ;
20+ }
3421
35- void rightView (TreeNode curr ,List <Integer >result ,int currDepth ) {
36- if (curr ==null ) {
37- return ;
38-
39- if (currDepth ==result .size ()) {
40- result .add (curr .val );
41-
42- rightView (curr .right ,result ,currDepth +1 );
43- rightView (curr .left ,result ,currDepth +1 );
44-
45-
22+ void rightView (TreeNode curr ,List <Integer >result ,int currDepth ) {
23+ if (curr ==null ) {
24+ return ;
25+
26+ if (currDepth ==result .size ()) {
27+ result .add (curr .val );
28+
29+ rightView (curr .right ,result ,currDepth +1 );
30+ rightView (curr .left ,result ,currDepth +1 );
31+
32+
4633
47- public static class Solution2 {
48- /**BFS the tree*/
49- public List <Integer >rightSideView (TreeNode root ) {
50- List <Integer >result =new ArrayList <>();
51- if (root ==null ) {
52- return result ;
53- }
54- Queue <TreeNode >q =new LinkedList <>();
55- q .offer (root );
56- while (!q .isEmpty ()) {
57- int size =q .size ();
58- for (int i =0 ;i <size ;i ++) {
59- TreeNode curr =q .poll ();
60- if (i ==size -1 ) {
61- result .add (curr .val );
62- }
63- if (curr .left !=null ) {
64- q .offer (curr .left );
65- }
66- if (curr .right !=null ) {
67- q .offer (curr .right );
68- }
69- }
70- }
71- return result ;
72- }
73- }
34+ public static class Solution2 {
35+ /**
36+ * BFS the tree
37+ */
38+ public List <Integer >rightSideView (TreeNode root ) {
39+ List <Integer >result =new ArrayList <>();
40+ if (root ==null ) {
41+ return result ;
42+ }
43+ Queue <TreeNode >q =new LinkedList <>();
44+ q .offer (root );
45+ while (!q .isEmpty ()) {
46+ int size =q .size ();
47+ for (int i =0 ;i <size ;i ++) {
48+ TreeNode curr =q .poll ();
49+ if (i ==size -1 ) {
50+ result .add (curr .val );
51+ }
52+ if (curr .left !=null ) {
53+ q .offer (curr .left );
54+ }
55+ if (curr .right !=null ) {
56+ q .offer (curr .right );
57+ }
58+ }
59+ }
60+ return result ;
61+ }
62+ }
7463
7564}