怎样制作html个人网站,网站百度收录查询,网站维护中什么意思,网站名称 域名leetcode地址#xff1a;二叉树中的最大路径和 二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点#xff0c;且不一定经过根节点。
路径和 是路径中各节点值的总…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, val0, leftNone, rightNone):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) # 应该输出42
go实现
package mainimport (fmtmath
)// 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
}
