题目
给定一个二叉树的 根节点 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
网友评论