Hex.*

LC513 - Find Bottom Left Tree Value

Posted on In
Leetcode: 137/2658 (57+66+14)

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

Solution

BFS

  • Traverse the tree from left to right, level by level
  • Save the first node of each layer
  • The answer saved by traversing to the bottom layer is the value in the lower left corner of the tree
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
# O(nm) time | O(n) space
# 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:
        if root is None:
            return 

        queue = [root]
        ans = 0
        while queue:
            level_len = len(queue)
            for i in range(level_len):
                pop_node = queue.pop(0)
                if i == 0:
                    ans = pop_node.val
                if pop_node.left:
                    queue.append(pop_node.left)
                if pop_node.right:
                    queue.append(pop_node.right)
        return ans
  • Traverse the tree from right to left, level by level
  • The last node traversed is the leftmost value of the tree
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
# O(n) time | O(n) space

# 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:
        if root is None:
            return 

        queue = [root]
        ans = 0
        while queue:
            pop_node = queue.pop(0)
            ans = pop_node.val

            if pop_node.right:
                queue.append(pop_node.right)
            if pop_node.left:
                queue.append(pop_node.left)
        return ans

#Runtime: 41 ms, faster than 97.73% of Python3 online submissions for Find Bottom Left Tree Value.
#Memory Usage: 16.3 MB, less than 62.72% of Python3 online submissions for Find Bottom Left Tree Value.