我要评论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
}
发表评论