leetcode--二叉树中的最大路径和

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 = val
        self.left = left
        self.right = right

# 最大路径和函数
def maxPathSum(root):
    def max_gain(node):
        nonlocal max_sum
        if 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   7
    root = 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)  # 应该输出42

go实现

package main

import (
	"fmt"
	"math"
)

// TreeNode 定义二叉树节点
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// maxPathSum 计算二叉树的最大路径和
func maxPathSum(root *TreeNode) int {
	maxSum := math.MinInt64

	var maxGain func(node *TreeNode) int
	maxGain = 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   7
	root := &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? = null
    var right: TreeNode? = null
}

// 最大路径和函数
fun maxPathSum(root: TreeNode?): Int {
    var maxSum = Int.MIN_VALUE

    fun 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   7
    val root = TreeNode(-10).apply {
        left = TreeNode(9)
        right = TreeNode(20).apply {
            left = TreeNode(15)
            right = TreeNode(7)
        }
    }

    val result = maxPathSum(root)
    println("最大路径和: $result")  // 应该输出42
}