題目

給定一個非空二叉樹，返回其最大路徑和。

本題中，路徑被定義為一條從樹中任意節點出發，達到任意節點的序列。該路徑至少包含一個節點，且不一定經過根節點。
leetcode problem 124

算例

輸出：6
解析：2—1—3為最大路徑和

輸出：42
解析：15—20—7為最大路徑和

func maxPathSum(root *TreeNode) int {//最小值maxSum := math.MinInt32var maxGain func(*TreeNode) intmaxGain = func(node *TreeNode) int {if node == nil {return 0}// 遞歸計算左右子節點的最大貢獻值// 只有在最大貢獻值大于 0 時，才會選取對應子節點leftGain := max(maxGain(node.Left), 0)rightGain := max(maxGain(node.Right), 0)// 節點的最大路徑和取決于該節點的值與該節點的左右子節點的最大貢獻值priceNewPath := node.Val + leftGain + rightGain// 更新答案maxSum = max(maxSum, priceNewPath)// 返回節點的最大貢獻值return node.Val + max(leftGain, rightGain)}maxGain(root)return maxSum }func max(x, y int) int {if x > y {return x}return y }

以樹種的每個節點為根節點進行遞歸，分別計算左子樹和右子數最大的路徑和，最后取最大值。

?

?

代碼地址：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-leetcode-/

?

?

總結

以上是生活随笔為你收集整理的二叉树中最大路径和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。