算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 二叉樹中的最大路徑和，我們先來看題面：https:///problems/binary-tree-maximum-path-sum/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.
題意本題中，路徑被定義為一條從樹中任意節(jié)點出發(fā)，沿父節(jié)點-子節(jié)點連接，達到任意節(jié)點的序列。該路徑至少包含一個節(jié)點，且不一定經(jīng)過根節(jié)點。解題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 好了，今天的文章就到這里，如果覺得有所收獲，請順手點個在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動力。
|
