难度: Medium
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
提示:
[1,104]-231 <= Node.val <= 231 - 1 注意：本题与主站 513 题相同： https://leetcode-cn.com/problems/find-bottom-left-tree-value/
运行时间: 27 ms
内存: 17.9 MB
# 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: TreeNode) -> int:
left = root.val
curH = -1
def dfs(node,height):
nonlocal left,curH
if not node:
return
if height>curH:
curH = height
left = node.val
dfs(node.left,height+1)
dfs(node.right,height+1)
dfs(root,0)
return left
此题解采用深度优先搜索（DFS）来寻找二叉树最底层最左边的节点值。使用两个非局部变量：left来记录当前找到的最左值，curH来记录当前的最大深度。DFS从根节点开始，对每个节点检查其深度是否超过了当前已知的最大深度curH。如果是，更新curH和left。DFS首先访问左子节点，确保最左的节点会被优先记录。
时间复杂度: O(n)
空间复杂度: O(n)
# 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: TreeNode) -> int:
left = root.val # 初始时，最左值设置为根节点值
curH = -1 # 初始最大深度为-1，表示还未开始遍历
def dfs(node, height):
nonlocal left, curH # 引用外层的变量
if not node:
return # 空节点直接返回
if height > curH:
curH = height # 更新当前最大深度
left = node.val # 更新最左值
dfs(node.left, height + 1) # 先递归左子树
dfs(node.right, height + 1) # 后递归右子树
dfs(root, 0) # 从根节点开始，高度为0
return left # 返回最左值
在这个问题中，目标是找到二叉树最底层的最左边的节点值。通过先访问左子节点再访问右子节点，确保了如果存在同一深度的多个节点，最左边的节点会首先被访问并记录。这是因为DFS会深入到最左边的路径直到无法继续为止，从而第一个达到最深层的节点肯定是最左边的节点。这样的访问顺序直接支持了题目的要求，即找到最底层最左边的值。
在DFS递归函数中，当当前节点的高度等于已知的最大深度时，不更新最左值是因为我们只需要在达到一个新的更深的层级时更新最左值。如果当前节点的高度仅等于已有的最大深度，说明我们已经在该深度层级访问过至少一个节点，且最左的节点已经被记录。此时更新最左值将导致不必要的覆盖，从而不再保持最左的特性。
在递归函数中，left和curH被定义为nonlocal变量，这意味着它们不是局部变量也不是全局变量，而是引用了外层作用域中的相同名称的变量。在递归过程中，每当找到一个更深层级的节点时，这两个变量都会被更新。由于它们是nonlocal变量，它们的改变会影响到所有递归调用中的同名变量。因此，无论递归在哪一层执行，left和curH总是被保持为最新更新的状态，确保了整个递归过程中这两个变量的一致性和准确性。