Tree
Depth-First Search
Breadth-First Search
Binary Tree
Description
Given the root
of 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 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2:
Input: root = [1,null,3]
Output: [1,3]
Example 3:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 100]
.
-100 <= Node.val <= 100
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def rightSideView ( self , root : Optional [ TreeNode ]) -> List [ int ]:
ans = []
if root is None :
return ans
q = deque ([ root ])
while q :
ans . append ( q [ - 1 ] . val )
for _ in range ( len ( q )):
node = q . popleft ()
if node . left :
q . append ( node . left )
if node . right :
q . append ( node . right )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List < Integer > rightSideView ( TreeNode root ) {
List < Integer > ans = new ArrayList <> ();
if ( root == null ) {
return ans ;
}
Deque < TreeNode > q = new ArrayDeque <> ();
q . offer ( root );
while ( ! q . isEmpty ()) {
ans . add ( q . peekLast (). val );
for ( int n = q . size (); n > 0 ; -- n ) {
TreeNode node = q . poll ();
if ( node . left != null ) {
q . offer ( node . left );
}
if ( node . right != null ) {
q . offer ( node . right );
}
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
vector < int > rightSideView ( TreeNode * root ) {
vector < int > ans ;
if ( ! root ) {
return ans ;
}
queue < TreeNode *> q {{ root }};
while ( ! q . empty ()) {
ans . emplace_back ( q . back () -> val );
for ( int n = q . size (); n ; -- n ) {
TreeNode * node = q . front ();
q . pop ();
if ( node -> left ) {
q . push ( node -> left );
}
if ( node -> right ) {
q . push ( node -> right );
}
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView ( root * TreeNode ) ( ans [] int ) {
if root == nil {
return
}
q := [] * TreeNode { root }
for len ( q ) > 0 {
ans = append ( ans , q [ len ( q ) - 1 ]. Val )
for n := len ( q ); n > 0 ; n -- {
node := q [ 0 ]
q = q [ 1 :]
if node . Left != nil {
q = append ( q , node . Left )
}
if node . Right != nil {
q = append ( q , node . Right )
}
}
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function rightSideView ( root : TreeNode | null ) : number [] {
if ( ! root ) {
return [];
}
let q = [ root ];
const ans : number [] = [];
while ( q . length ) {
const nextq : TreeNode [] = [];
ans . push ( q . at ( - 1 ) ! . val );
for ( const { left , right } of q ) {
if ( left ) {
nextq . push ( left );
}
if ( right ) {
nextq . push ( right );
}
}
q = nextq ;
}
return ans ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std :: cell :: RefCell ;
use std :: collections :: VecDeque ;
use std :: rc :: Rc ;
impl Solution {
pub fn right_side_view ( root : Option < Rc < RefCell < TreeNode >>> ) -> Vec < i32 > {
let mut res = vec! [];
if root . is_none () {
return res ;
}
let mut q = VecDeque :: new ();
q . push_back ( root );
while ! q . is_empty () {
let n = q . len ();
res . push ( q [ n - 1 ]. as_ref (). unwrap (). borrow (). val );
for _ in 0 .. n {
if let Some ( node ) = q . pop_front (). unwrap () {
let mut node = node . borrow_mut ();
if node . left . is_some () {
q . push_back ( node . left . take ());
}
if node . right . is_some () {
q . push_back ( node . right . take ());
}
}
}
}
res
}
}
Solution 2
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def rightSideView ( self , root : Optional [ TreeNode ]) -> List [ int ]:
def dfs ( node , depth ):
if node is None :
return
if depth == len ( ans ):
ans . append ( node . val )
dfs ( node . right , depth + 1 )
dfs ( node . left , depth + 1 )
ans = []
dfs ( root , 0 )
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List < Integer > ans = new ArrayList <> ();
public List < Integer > rightSideView ( TreeNode root ) {
dfs ( root , 0 );
return ans ;
}
private void dfs ( TreeNode node , int depth ) {
if ( node == null ) {
return ;
}
if ( depth == ans . size ()) {
ans . add ( node . val );
}
dfs ( node . right , depth + 1 );
dfs ( node . left , depth + 1 );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
vector < int > rightSideView ( TreeNode * root ) {
vector < int > ans ;
function < void ( TreeNode * , int ) > dfs = [ & ]( TreeNode * node , int depth ) {
if ( ! node ) {
return ;
}
if ( depth == ans . size ()) {
ans . emplace_back ( node -> val );
}
dfs ( node -> right , depth + 1 );
dfs ( node -> left , depth + 1 );
};
dfs ( root , 0 );
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView ( root * TreeNode ) ( ans [] int ) {
var dfs func ( * TreeNode , int )
dfs = func ( node * TreeNode , depth int ) {
if node == nil {
return
}
if depth == len ( ans ) {
ans = append ( ans , node . Val )
}
dfs ( node . Right , depth + 1 )
dfs ( node . Left , depth + 1 )
}
dfs ( root , 0 )
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function rightSideView ( root : TreeNode | null ) : number [] {
const ans = [];
const dfs = ( node : TreeNode | null , depth : number ) => {
if ( ! node ) {
return ;
}
if ( depth == ans . length ) {
ans . push ( node . val );
}
dfs ( node . right , depth + 1 );
dfs ( node . left , depth + 1 );
};
dfs ( root , 0 );
return ans ;
}