124. 二叉樹中的最大路徑和
題目來源：力扣（LeetCode）https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
題目
給定一個非空二叉樹精堕，返回其最大路徑和砸王。
本題中馆揉，路徑被定義為一條從樹中任意節(jié)點出發(fā)，達(dá)到任意節(jié)點的序列管挟。該路徑至少包含一個節(jié)點占锯，且不一定經(jīng)過根節(jié)點。
示例 1:
輸入: [1,2,3]
1
/ \
2 3
輸出: 6
示例 2:
輸入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
輸出: 42
解題思路
思路：遞歸
題目中所給出的路徑概念是指【一條從樹中任意節(jié)點出發(fā)挺身，達(dá)到任意節(jié)點的序列豆励。該路徑至少包含一個節(jié)點，且不一定經(jīng)過根節(jié)點】瞒渠。
也就是說良蒸，要求出路徑和，得計算節(jié)點能提供的最大貢獻(xiàn)值伍玖。
對于節(jié)點能提供的貢獻(xiàn)值嫩痰，分為如下部分：
- 空節(jié)點提供的貢獻(xiàn)值為 0；
- 對于非空節(jié)點提供的貢獻(xiàn)值窍箍，等于當(dāng)前節(jié)點的值與其子節(jié)點中提供最大貢獻(xiàn)值的和串纺。
現(xiàn)在以示例 1 來分析說明下：
輸入: [1,2,3]
1
/ \
2 3
在這里葉子節(jié)點 2,3，能提供的貢獻(xiàn)值就是 2椰棘， 3纺棺。
而葉子節(jié)點 1，能夠提供的貢獻(xiàn)值為 1+2 或 1+3邪狞。
那我們假設(shè)：如果節(jié)點 1 前面還有父節(jié)點祷蝌，那么這里可能的路徑就會變成：
- 2 + 1 + 3
- 2 + 1 + 1 的父節(jié)點
- 3 + 1 + 1 的父節(jié)點
其中第一種情況，就是求節(jié)點的最大路徑和帆卓。這里節(jié)點的最大路徑和取決于該節(jié)點與其左右子節(jié)點的最大貢獻(xiàn)值之和巨朦。當(dāng)然，在這里剑令，如果子節(jié)點的貢獻(xiàn)值為負(fù)糊啡，則選擇不納入。因為負(fù)數(shù)的貢獻(xiàn)值添加進(jìn)來反而會讓結(jié)果變小吁津。
對于第二種和第三種情況來說棚蓄，這里就是遞歸求得左右子節(jié)點的貢獻(xiàn)值，從中取更優(yōu)的方案。
這里最主要的就是維護一個存儲最大路徑和的變量 max_path_sum梭依，遞歸的過程中維護更新這個值挣柬，從而求得最大值。
具體的代碼實現(xiàn)如下睛挚。
代碼實現(xiàn)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
# 存儲最大路徑和
self.max_path_sum = float('-inf')
def maxPathSum(self, root: TreeNode) -> int:
def max_contr(node):
# 遞歸求節(jié)點最大貢獻(xiàn)值
# 同時維護經(jīng)過節(jié)點的最大路徑和
# 空節(jié)點的貢獻(xiàn)值為 0
if not node:
return 0
# 遞歸計算左子節(jié)點的貢獻(xiàn)值邪蛔，
left = max(0, max_contr(node.left))
# 遞歸計算右子節(jié)點的貢獻(xiàn)值
right = max(0, max_contr(node.right))
# 經(jīng)過當(dāng)前節(jié)點的最大路徑和
self.max_path_sum = max(self.max_path_sum, left + node.val + right)
# 當(dāng)前節(jié)點的貢獻(xiàn)值，取左右子節(jié)點中的更優(yōu)方案
node_contr = node.val + max(0, max(left, right))
# 這里返回的貢獻(xiàn)值是給當(dāng)前節(jié)點的上游節(jié)點
return node_contr
max_contr(root)
return self.max_path_sum
實現(xiàn)結(jié)果
總結(jié)
- 從題目中得到的信息可以知道扎狱，要求最大路徑和侧到，需要求得節(jié)點能夠提供的貢獻(xiàn)值。
- 對于節(jié)點而言淤击，提供的貢獻(xiàn)值分為兩部分：
- 空節(jié)點的貢獻(xiàn)值為 0匠抗；
- 對于非空節(jié)點而言，當(dāng)前節(jié)點能提供的貢獻(xiàn)值為當(dāng)前節(jié)點的值與其子節(jié)點中能提供的最大貢獻(xiàn)值之和
- 對于非空節(jié)點而言污抬，我們需要遞歸的方法求得每個節(jié)點的貢獻(xiàn)值汞贸。同時，需要維護最大路徑和印机，在這里矢腻，該節(jié)點的路徑和取決于當(dāng)前節(jié)點的值與其左右子節(jié)點的最大貢獻(xiàn)值。
- 這里需要注意：當(dāng)貢獻(xiàn)值為負(fù)時射赛，不計入節(jié)點的最大路徑和多柑。
文章原創(chuàng)，如果覺得寫得還好楣责，歡迎關(guān)注點贊竣灌。微信公眾號《書所集錄》同步更新，同樣歡迎關(guān)注點贊秆麸。
