Skip to content

Files

Latest commit

Jul 23, 2023
e1b8af0 · Jul 23, 2023

History

History

0513-Find Bottom Left Tree Value

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
No commit message
Jul 23, 2023
No commit message
Jul 23, 2023
No commit message
Jul 23, 2023
No commit message
Jul 23, 2023

513. Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input:
    2
   / \
  1   3
Output:
1

Example 2:

Input:
        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7
Output:
7

Note:

You may assume the tree (i.e., the given root node) is not NULL.

Solutions (Python)

1. BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        curr_level = [root]

        while curr_level:
            ret = curr_level[0].val
            next_level = [node.left for node in curr_level if node.left]
            next_level.extend(node.right for node in curr_level if node.right)
            curr_level = next_level

        return ret

2. DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        def dfs(root: TreeNode, depth: int) -> (int, int):
            ori_depth = depth
            val, depth = root.val, depth

            if root.left:
                val, depth = dfs(root.left, ori_depth + 1)
            if root.right:
                right_val, right_depth = dfs(root.right, ori_depth + 1)
                if right_depth > depth:
                    val, depth = right_val, right_depth

            return val, depth

        return dfs(root, 1)[0]