513. Find Bottom Left Tree Value
Medium LeetCodeGiven 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
How to solve the problem
Code
- BFS
Python
# 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:
# Initialize a queue with the root node
# We will use BFS (breadth-first search), but process right child first!
q = deque([root])
# Perform BFS traversal
while q:
# Pop the current node from the front of the queue
node = q.popleft()
# IMPORTANT: Add right child first
# This ensures that the last node we visit will be the bottom-left node
if node.right:
q.append(node.right)
# Add left child
if node.left:
q.append(node.left)
# After the loop, 'node' will point to the last node visited,
# which is the bottom-left value of the tree
return node.val
Complexity
- Time complexity: O(n), n == number of nodes
- Space complexity: O(n)
Comments
No comments yet. Be the first to comment!