Tree - 124. Binary Tree Maximum Path Sum
Tree - 124. Binary Tree Maximum Path Sum
ppxai
发布于 2020-09-23 17:30:58
发布于 2020-09-23 17:30:58
124. Binary Tree Maximum Path Sum
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6Example 2:
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42思路：
题目意思是找出二叉树最大的一个路径和，这个路径不需要一定经过root节点，但是必须包含一个节点，题目还是比较阴险，因为如果都是负数，也得找出那个最大的，比如只有一个root节点，值为-1，也得返回-1，做法就是使用递归求解，如果root不为空，那么就找左右节点，看左右节点的从左走和从右走的值的最大值，同时记录下最大值，然后递归返回到父节点依次求解。注意递归返回的时候，不是返回最终结果的最大值，只是只经过一个子节点的那个路径的最大值。
代码：
go：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// import "math"
func maxPathSum(root *TreeNode) int {
if root == nil {
return math.MinInt32
}
var res = math.MinInt32
dfs(root, &res)
return res
}
func dfs(node *TreeNode, res *int) int {
if node == nil {
return 0
}
left := max(dfs(node.Left, res), 0)
right := max(dfs(node.Right, res), 0)
// 记录最大路径和
*res = max(*res, node.Val + left + right)
return node.Val + max(left, right)
}
func max(i, j int) int {
if i > j {
return i
}
return j
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019年08月20日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读