Find Bottom Left Tree Value - Python 3 Solution


  • 0
    C
    class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    
    
    class Solution(object):
        def findBottomLeftValue(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root is None:
                return None
    
            return self.search(root, 0)[0]
        
        def search(self, root, level):
            if root.left is None and root.right is None:
                return root.val, level
            if root.left is None:
                return self.search(root.right, level+1)
            if root.right is None:
                return self.search(root.left, level+1)
            
            left_bottomLeftVal, left_bottomLeftLevel = self.search(root.left, level+1)
            right_bottomLeftVal, right_bottomLeftLevel = self.search(root.right, level+1)
            if left_bottomLeftLevel >= right_bottomLeftLevel:
                return left_bottomLeftVal, left_bottomLeftLevel
            else:
                return right_bottomLeftVal, right_bottomLeftLevel
    

    The problem can be solved recursively.
    Each time we find the bottom left value of both left and right subTree.
    Then if left subTree has a deeper level, return left subTree's bottom left value, else return right subTree's bottom left value


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.