LeetCode 513. 找树左下角的值

题目

给定一个二叉树的 根节点 root，请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。

例：
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

方法：递归

要求找到二叉树的最后一行（深度最大）的最左边的叶子节点的值，所以可以使用前序遍历，先搜索左边

• max_depth 用来记录遇见的最大的深度，max_value 用来记录该最大深度最左边叶子节点的值
• 首先，判断此节点是否为叶子节点，若为叶子节点，则判断该节点的深度是否大于已知的最大深度，若大于的话，则更新最大深度和最左叶子节点的值
• 其次判断该节点是否存在左右子树，若存在则表示此时并不是该二叉树的最大深度，那么继续调用该函数

# 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: Optional[TreeNode]) -> int:
        max_depth = -1
        max_value = 0

        def traversal(root, depth):
            nonlocal max_depth, max_value
            if root.left == None and root.right == None:
                if depth > max_depth:
                    max_depth = depth
                    max_value = root.val
            if root.left:
                traversal(root.left, depth + 1)
            if root.right:
                traversal(root.right, depth + 1)

        traversal(root, 0)
        return max_value

相关知识

• nonlocal：
  关键字，用于在函数中修改不可变类型的外层变量（非全局变量），若只是读取外层变量或该变量为可变的，则不需要添加此关键字

报错

• Invalid Syntax：
  nonlocal 关键字只有在 python3 时才会起作用
  

参考

代码相关：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html