生活随笔
收集整理的這篇文章主要介紹了
二叉树中的最大路径和
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
給定一個非空二叉樹，返回其最大路徑和。
本題中，路徑被定義為一條從樹中任意節(jié)點出發(fā)，達(dá)到任意節(jié)點的序列。該路徑至少包含一個節(jié)點，且不一定經(jīng)過根節(jié)點。
輸入
: [1,2,3]1/ \
2 3輸出
: 6
輸入
: [-10,9,20,null
,null
,15,7]-10/ \
9 20/ \
15 7輸出
: 42
來源：力扣（LeetCode）
- 思路
求出每一個點的最大貢獻(xiàn)。當(dāng)節(jié)點是葉子節(jié)點的時候，最大貢獻(xiàn)就是val的值，最大和的值為葉子節(jié)點值和最大和初始值的最大的一個考慮；當(dāng)節(jié)點有子節(jié)點的時候，則節(jié)點最大貢獻(xiàn)為節(jié)點val加上左右節(jié)點最大貢獻(xiàn)的最大值，最大和為左右節(jié)點最大貢獻(xiàn)加上該節(jié)點val值與全局最大和相比較的最大值。 - c++
class Solution
{
private
:int maxSum
= INT_MIN
;
public
:int maxGain(TreeNode
*node
) {if (node
== NULL) {return 0;}int maxLeft
= max(maxGain(node
->left
), 0);int maxRight
= max(maxGain(node
->right
), 0);int p
= node
->val
+ maxLeft
+ maxRight
;maxSum
= max(maxSum
, p
);return node
->val
+ max(maxLeft
, maxRight
);}int maxPathSum(TreeNode
* root
) {maxGain(root
);return maxSum
;}
};
func
maxPathSum(root
*TreeNode
) int {maxSum
:= math
.MinInt32var maxGain
func(*TreeNode
) intmaxGain
= func(node
*TreeNode
) int {if node
== nil
{return 0}maxLeft
:= max(maxGain(node
.Left
), 0)maxRight
:= max(maxGain(node
.Right
), 0)p
:= node
.Val
+ maxLeft
+ maxRightmaxSum
= max(maxSum
, p
)return node
.Val
+ max(maxLeft
, maxRight
)}maxGain(root
)return maxSum
}func
max(a
, b
int) int {if a
> b
{return a
}return b
}
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass
Solution(object
):def
__init__(self
):self
.maxSum
= float('-inf')def
maxPathSum(self
, root
):"""
:type root
: TreeNode
:rtype
: int"""def
maxGain(self
, node
):if not node
:return 0maxLeft
= max(maxGain(self
, node
.left
), 0)maxRight
= max(maxGain(self
, node
.right
), 0)p
= node
.val
+ maxLeft
+ maxRightself
.maxSum
= max(self
.maxSum
, p
)return node
.val
+ max(maxLeft
, maxRight
)maxGain(self
, root
)return self
.maxSum
總結(jié)
以上是生活随笔為你收集整理的二叉树中的最大路径和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
