Tree
Depth-First Search
Breadth-First Search
Binary Tree
Description
Given the root
of a binary tree, return the leftmost value in the last row of the tree.
Example 1:
Input: root = [2,1,3]
Output: 1
Example 2:
Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7
Constraints:
The number of nodes in the tree is in the range [1, 104 ]
.
-231 <= Node.val <= 231 - 1
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 # 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 findBottomLeftValue ( self , root : Optional [ TreeNode ]) -> int :
q = deque ([ root ])
ans = 0
while q :
ans = q [ 0 ] . 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 /**
* 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 int findBottomLeftValue ( TreeNode root ) {
Queue < TreeNode > q = new ArrayDeque <> ();
q . offer ( root );
int ans = 0 ;
while ( ! q . isEmpty ()) {
ans = q . peek (). val ;
for ( int i = q . size (); i > 0 ; -- i ) {
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 /**
* 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 :
int findBottomLeftValue ( TreeNode * root ) {
queue < TreeNode *> q {{ root }};
int ans = 0 ;
while ( ! q . empty ()) {
ans = q . front () -> val ;
for ( int i = q . size (); i ; -- i ) {
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 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findBottomLeftValue ( root * TreeNode ) int {
q := [] * TreeNode { root }
ans := 0
for len ( q ) > 0 {
ans = q [ 0 ]. Val
for i := len ( q ); i > 0 ; i -- {
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 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 /**
* 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 findBottomLeftValue ( root : TreeNode | null ) : number {
let ans = 0 ;
const q = [ root ];
while ( q . length ) {
ans = q [ 0 ]. val ;
for ( let i = q . length ; i ; -- i ) {
const node = q . shift ();
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42 // 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 find_bottom_left_value ( root : Option < Rc < RefCell < TreeNode >>> ) -> i32 {
let mut queue = VecDeque :: new ();
queue . push_back ( root );
let mut res = 0 ;
while ! queue . is_empty () {
res = queue . front (). unwrap (). as_ref (). unwrap (). borrow_mut (). val ;
for _ in 0 .. queue . len () {
let node = queue . pop_front (). unwrap ();
let mut node = node . as_ref (). unwrap (). borrow_mut ();
if node . left . is_some () {
queue . push_back ( node . left . take ());
}
if node . right . is_some () {
queue . push_back ( node . right . take ());
}
}
}
res
}
}
Solution 2
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 findBottomLeftValue ( self , root : Optional [ TreeNode ]) -> int :
def dfs ( root , curr ):
if root is None :
return
dfs ( root . left , curr + 1 )
dfs ( root . right , curr + 1 )
nonlocal ans , mx
if mx < curr :
mx = curr
ans = root . val
ans = mx = 0
dfs ( root , 1 )
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 /**
* 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 int ans = 0 ;
private int mx = 0 ;
public int findBottomLeftValue ( TreeNode root ) {
dfs ( root , 1 );
return ans ;
}
private void dfs ( TreeNode root , int curr ) {
if ( root == null ) {
return ;
}
dfs ( root . left , curr + 1 );
dfs ( root . right , curr + 1 );
if ( mx < curr ) {
mx = curr ;
ans = root . val ;
}
}
}
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 /**
* 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 :
int ans = 0 ;
int mx = 0 ;
int findBottomLeftValue ( TreeNode * root ) {
dfs ( root , 1 );
return ans ;
}
void dfs ( TreeNode * root , int curr ) {
if ( ! root ) return ;
dfs ( root -> left , curr + 1 );
dfs ( root -> right , curr + 1 );
if ( mx < curr ) {
mx = curr ;
ans = root -> val ;
}
}
};
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 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findBottomLeftValue ( root * TreeNode ) int {
ans , mx := 0 , 0
var dfs func ( * TreeNode , int )
dfs = func ( root * TreeNode , curr int ) {
if root == nil {
return
}
dfs ( root . Left , curr + 1 )
dfs ( root . Right , curr + 1 )
if mx < curr {
mx = curr
ans = root . Val
}
}
dfs ( root , 1 )
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 /**
* 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 findBottomLeftValue ( root : TreeNode | null ) : number {
let mx = 0 ;
let ans = 0 ;
function dfs ( root , curr ) {
if ( ! root ) {
return ;
}
dfs ( root . left , curr + 1 );
dfs ( root . right , curr + 1 );
if ( mx < curr ) {
mx = curr ;
ans = root . val ;
}
}
dfs ( root , 1 );
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 // 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 {
fn dfs ( root : & Option < Rc < RefCell < TreeNode >>> , cur : i32 , max : & mut i32 , res : & mut i32 ) {
if root . is_none () {
return ;
}
let root = root . as_ref (). unwrap (). borrow ();
Self :: dfs ( & root . left , cur + 1 , max , res );
Self :: dfs ( & root . right , cur + 1 , max , res );
if * max < cur {
* max = cur ;
* res = root . val ;
}
}
pub fn find_bottom_left_value ( root : Option < Rc < RefCell < TreeNode >>> ) -> i32 {
let mut max = 0 ;
let mut res = 0 ;
Self :: dfs ( & root , 1 , & mut max , & mut res );
res
}
}