513. 找树左下角的值

# 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 __init__(self):
        self.depth = 1
        self.maxdepth = 0
        self.result = None 
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        # 方法一：bfs 方法
        '''
        result,result_sub,list_ = [],[],[]
        if root: list_.append(root)
        while list_:
            size = len(list_)
            while size:
                size -= 1
                root = list_.pop(0)
                result_sub.append(root.val)
                if root.left:
                    list_.append(root.left)
                if root.right:
                    list_.append(root.right)
            result.append(result_sub)
            result_sub = []
        print(result)
        return result[-1][0]
        '''
        # 方法二：递归回溯,找深度最深的一层的从左数第一个节点的值。
        if root.left==None and root.right==None: # 基线条件
            if self.depth > self.maxdepth:                 # 基线条件
                self.maxdepth = self.depth 
                self.result = root.val 
        if root.left:
            self.depth += 1
            left_value = self.findBottomLeftValue(root.left)
            self.depth -= 1
        if root.right:
            self.depth += 1
            right_value = self.findBottomLeftValue(root.right)
            self.depth -= 1
        return self.result