?LeetCode刷題實(shí)戰(zhàn)124：二叉樹中的最大路徑和
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any node sequence from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
題意
解題
邊界判斷
遞歸找出左右子樹最大的gain，小于0就不選。
取以當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)的最大值和root為根節(jié)點(diǎn)最大值為最大路徑和
返回每個節(jié)點(diǎn)作為根節(jié)點(diǎn)的最大路徑作為子樹的最大路徑。
class?Solution:
????def?maxPathSum(self, root: TreeNode)?-> int:
????????
????????def?max_gain(node):
????????????nonlocal?max_sum
????????????if?not?node:return?0
????????????left_max = max(max_gain(node.left), 0)
????????????right_max = max(max_gain(node.right),0)
????????????new_price = node.val + left_max + right_max
????????????max_sum = max(max_sum, new_price)
????????????return?node.val + max(left_max, right_max)
????????max_sum = float('-inf')
????????max_gain(root)
????????return?max_sum