日野弥生：勉強しよう
LeetCode 543 - 二叉树的直径
发表于2025年03月03日
递归解题,整体思路都是后根遍历，先求出左右子树的结果，再对直径进行计算。
本题关键点在于正确地理解二叉树的直径，如果二叉树直径经过根节点，那么最大直径为左子树和右子树的深度和；如果二叉树直径不经过根节点，那最大直径为左右子树的直径的最大值。
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
# 存储整棵树的最大直径
maxDiam = 0
def getDepthAndDiam(root: Optional[TreeNode]):
# 变量会在函数内被改变的话，需要写这句
nonlocal maxDiam
# 元组的第一个元素是深度，第二个是当前子树的直径，如果是空节点，自然二者皆为0
if not root:
return (0, 0)
# 后根遍历
leftDepAndDiam = getDepthAndDiam(root.left)
rightDepAndDiam = getDepthAndDiam(root.right)
# 如果经过根节点，则直径为左右子树深度之和
first = leftDepAndDiam[0] + rightDepAndDiam[0]
# 如果不经过根节点，则最大直径为两子树的直径的最大值
second = max(leftDepAndDiam[1], rightDepAndDiam[1])
# 二者最大值更新为当前的最大直径
maxDiam = maxDiam if maxDiam > max(first, second) else max(first, second)
# 返回的元组第一个自然为当前深度，第二个即当前直径
return (max(leftDepAndDiam[0], rightDepAndDiam[0]) + 1, second)
result = getDepthAndDiam(root)
return maxDiam