<p>Given the <code>root</code> of a binary tree, return the leftmost value in the last row of the tree.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/14/tree1.jpg" style="width: 302px; height: 182px;" />
<pre>
<strong>Input:</strong> root = [2,1,3]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/14/tree2.jpg" style="width: 432px; height: 421px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4,null,5,6,null,null,7]
<strong>Output:</strong> 7
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 10<sup>4</sup>]</code>.</li>
	<li><code>-2<sup>31</sup> &lt;= Node.val &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

# 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

#2023/05/20
'''
因为对于当前节点来说，要知道他左子树的最左侧节点和右子树的最左侧节点，才能知道当前应该返回什么，所以用后序遍历。
返回左子树还是右子树的，关键是看二者叶子节点的深度，所以还要记录当前node的深度。利用后序遍历先左后右的性质，可以先根据左子树来更新，只有当右子树大于当前深度时，才更新成右子树，所以还需要一个变量记录结果和当前深度
'''
# class Solution:
#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
#         self.currVal=0
#         self.maxHeight=0
#         def helper(node,height):
#             if node==None:
#                 return
#             helper(node.left,height+1)
#             helper(node.right,height+1)
#             if height>self.maxHeight:
#                 self.maxHeight=height
#                 self.currVal=node.val
#         helper(root,1)
#         return self.currVal    


# from collections import deque
# class Solution:
#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
#         if root==None:
#             return 0
#         q=deque()
#         q.append(root)
#         res=float("-inf")
#         while q:
#             size=len(q)
#             for i in range(size):
#                 curr=q.popleft()
#                 #最后一层拿出来的第一个
#                 if i==0:
#                     res=curr.val
#                 if curr.left:
#                     q.append(curr.left)
#                 if curr.right:
#                     q.append(curr.right)
#         return res


#2023/08/01
# from collections import deque
# class Solution:
#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
#         q=deque()
#         q.append(root)
#         res=root.val
#         while q:
#             size=len(q)
#             for i in range(size):
#                 curr=q.popleft()
#                 if i==0:
#                     res=curr.val
#                 if curr.left:
#                     q.append(curr.left)
#                 if curr.right:
#                     q.append(curr.right)
#         return res



# class Solution:
#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
#         self.maxLen=0
#         self.leftVal=0
#         def helpFuc(node,height):
#             if node.left==None and node.right==None:
#                 if height>self.maxLen:
#                     self.maxLen=height
#                     self.leftVal=node.val
#             if node.left:
#                 helpFuc(node.left,height+1)
#             if node.right:
#                 helpFuc(node.right,height+1)
#         helpFuc(root,1)
#         return self.leftVal


#2023/08/06
# from collections import deque
# class Solution:
#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
#         q=deque()
#         q.append(root)
#         res=root.val
#         while q:
#             size=len(q)
#             for i in range(size):
#                 curr=q.popleft()
#                 if i==0:
#                     res=curr.val
#                 if curr.left:
#                     q.append(curr.left)
#                 if curr.right:
#                     q.append(curr.right)
#         return res


# class Solution:
#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
#         self.res=root.val
#         self.high=0
#         self.helpFuc(root,0)
#         return self.res
#     def helpFuc(self,root,level):
#         if root==None:
#             return 
#         if root.left==None and root.right==None:
#             if self.high<level:
#                 self.res=root.val
#                 self.high=level
#         self.helpFuc(root.left,level+1)
#         self.helpFuc(root.right,level+1)


#2024/06/01
'''
最后一排最左边一个
BFS每层更新最左边就好了
'''
# from collections import deque
# class Solution:
#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
#         q=deque()
#         q.append(root)
#         res=0
#         while q:
#             size=len(q)
#             for i in range(size):
#                 curr=q.popleft()
#                 if i==0:
#                     res=curr.val
#                 if curr.left:
#                     q.append(curr.left)
#                 if curr.right:
#                     q.append(curr.right)
#         return res

'''
递归，先call左子树，再call右子树
用一个level来控制是不是当前这一行的第一个
所以还需要一个高度来track 当前的高度
如果当前高度小于level了，就说明到了新的一层了
'''
# class Solution:
#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
#         self.res=root.val
#         self.h=0
#         self.helper(root,1)
#         return self.res
#     def helper(self,root,level):
#         if root==None:
#             return
#         #一旦进到新的一层了就更新
#         if self.h<level:
#             self.h+=1
#             self.res=root.val
#         self.helper(root.left,level+1)
#         self.helper(root.right,level+1)
    

#2024/09/16
'''
一旦进到了新的一层，就去更新答案（如果先左再右）

怎么知道进到新的一层。一个全局变量track当前更新到的层数，一个level跟着递归走
一旦level大于track的高度了，那就更新
'''
# class Solution:
#     def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
#         if root==None:
#             return 0
#         self.res=[]
#         self.helper(root,0)
#         return self.res[-1][0]
    
#     def helper(self,root,level):
#         if level==len(self.res):
#             self.res.append([])
#         self.res[level].append(root.val)
#         if root.left:
#             self.helper(root.left,level+1)
#         if root.right:
#             self.helper(root.right,level+1)



class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        self.res=root.val
        self.h=0
        self.helper(root,1)
        return self.res
    
    def helper(self,root,level):
        if root==None:
            return 
        if self.h<level:
            self.h+=1
            self.res=root.val
        self.helper(root.left,level+1)
        self.helper(root.right,level+1)
19600