leetcode地址：二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000
实现思路
在二叉树中，路径被定义为一条节点序列，其中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。路径至少包含一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。给定一个二叉树的根节点，要求返回其最大路径和。
要找到最大路径和，我们需要考虑路径可以从任意节点开始和结束，并且路径可以不经过根节点。这意味着我们需要检查每个节点可能作为路径起点和终点的情况。
定义递归函数
我们定义一个递归函数 max_gain(node) 来计算节点的最大贡献值。这个函数计算从当前节点出发，延伸到左右子树所能获得的最大路径和。
计算当前节点的最大贡献值
如果当前节点为空，返回0。
计算左子树的最大贡献值，记为 left_gain。如果 left_gain 是负值，设置为0，因为负值不会增加路径和。
计算右子树的最大贡献值，记为 right_gain。如果 right_gain 是负值，设置为0，因为负值不会增加路径和。
计算路径和
计算当前节点作为路径最高点的路径和，即 node.val + left_gain + right_gain。
更新全局最大路径和。
返回节点的最大贡献值
返回节点的最大贡献值，即 node.val + max(left_gain, right_gain)，因为路径只能选择一个子树继续延伸。
代码实现
# 定义二叉树节点类
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right# 最大路径和函数
def maxPathSum(root):def max_gain(node):nonlocal max_sumif not node:return 0# 递归计算左子树和右子树的最大贡献值left_gain = max(max_gain(node.left), 0)right_gain = max(max_gain(node.right), 0)# 当前节点的路径和current_path_sum = node.val + left_gain + right_gain# 更新最大路径和max_sum = max(max_sum, current_path_sum)# 返回节点的最大贡献值return node.val + max(left_gain, right_gain)max_sum = float('-inf')max_gain(root)return max_sum# 测试示例
if __name__ == "__main__":# 创建测试二叉树# -10# / \# 9 20# / \# 15 7root = TreeNode(-10)root.left = TreeNode(9)root.right = TreeNode(20)root.right.left = TreeNode(15)root.right.right = TreeNode(7)result = maxPathSum(root)print("最大路径和:", result) # 应该输出42go实现
package mainimport ("fmt""math"
)// TreeNode 定义二叉树节点
type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}// maxPathSum 计算二叉树的最大路径和
func maxPathSum(root *TreeNode) int {maxSum := math.MinInt64var maxGain func(node *TreeNode) intmaxGain = func(node *TreeNode) int {if node == nil {return 0}// 递归计算左子树和右子树的最大贡献值leftGain := max(maxGain(node.Left), 0)rightGain := max(maxGain(node.Right), 0)// 当前节点的路径和currentPathSum := node.Val + leftGain + rightGain// 更新最大路径和if currentPathSum > maxSum {maxSum = currentPathSum}// 返回节点的最大贡献值return node.Val + max(leftGain, rightGain)}maxGain(root)return maxSum
}// 辅助函数，取两个整数中的最大值
func max(a, b int) int {if a > b {return a}return b
}// 测试示例
func main() {// 创建测试二叉树// -10// / \// 9 20// / \// 15 7root := &TreeNode{Val: -10}root.Left = &TreeNode{Val: 9}root.Right = &TreeNode{Val: 20}root.Right.Left = &TreeNode{Val: 15}root.Right.Right = &TreeNode{Val: 7}result := maxPathSum(root)fmt.Printf("最大路径和: %d\n", result) // 应该输出42
}kotlin实现
// 定义二叉树节点类
class TreeNode(var `val`: Int) {var left: TreeNode? = nullvar right: TreeNode? = null
}// 最大路径和函数
fun maxPathSum(root: TreeNode?): Int {var maxSum = Int.MIN_VALUEfun maxGain(node: TreeNode?): Int {if (node == null) return 0// 递归计算左子树和右子树的最大贡献值val leftGain = maxOf(maxGain(node.left), 0)val rightGain = maxOf(maxGain(node.right), 0)// 当前节点的路径和val currentPathSum = node.`val` + leftGain + rightGain// 更新最大路径和maxSum = maxOf(maxSum, currentPathSum)// 返回节点的最大贡献值return node.`val` + maxOf(leftGain, rightGain)}maxGain(root)return maxSum
}// 测试示例
fun main() {// 创建测试二叉树// -10// / \// 9 20// / \// 15 7val root = TreeNode(-10).apply {left = TreeNode(9)right = TreeNode(20).apply {left = TreeNode(15)right = TreeNode(7)}}val result = maxPathSum(root)println("最大路径和: $result") // 应该输出42
}
)
