赞
踩
# 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: ### 0103 递归(88 ms,22.2 MB) def maxPathSum(self, root: TreeNode) -> int: # 初始化最大值为负无穷 self.maxSum = float('-inf') # 定义计算每个节点最大贡献的递归函数 def maxGain(node): # 递归终止条件 if not node: return 0 # 递归计算当前节点左、右孩子的最大贡献 leftGain = max(maxGain(node.left), 0) rightGain = max(maxGain(node.right), 0) # 更新最大路径的值 # node.val + leftGain + rightGain表示:当前这棵子树的 总的 最大贡献 self.maxSum = max(self.maxSum, node.val + leftGain + rightGain) # 返回此节点的最大贡献:仅与一个孩子节点有关! return node.val + max(leftGain, rightGain) # 开始递归 maxGain(root) return self.maxSum
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。