题目链接:124. 二叉树中的最大路径和
题目描述:
思路:这类题目一般可以通过dfs方式完成,首先我们明白,想要获取这棵二叉树中的最大路径和,那么我们需要知道以每个节点为根的最大路径和,最后找最大的就可以得到答案。那么如何找一个节点的最大路径和呢,一个节点的最大路径和为它的左右两边节点的贡献值与当前这个节点值相加的结果,因此,在dfs时候我们需要获取的就是当前节点的最大贡献值,最终每个节点最多会被遍历一次,总的时间复杂度为O(n)。
代码:
func maxPathSum(root *TreeNode) int {
maxSum := math.MinInt32
dfs(root,&maxSum)
return maxSum
}
func dfs(node *TreeNode, maxSum *int) int {
if node == nil {
return 0
}
leftVal := max(dfs(node.Left, maxSum), 0)
rightVal := max(dfs(node.Right, maxSum), 0)
curPathSum := node.Val + leftVal + rightVal
*maxSum = max(*maxSum, curPathSum)
return node.Val + max(leftVal,rightVal)
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
这题还能用划分子问题的方式思考,变成动态规划,思路和dfs差不多,下面摘自评论区大佬解答,便于理解:
这题目的难点在于理解题意和转化题意。
我们可以结合 数组的最大子数组和 的思路去解题。
1. 「可以从任意节点出发, 到达任意节点」 的路径,
一定是先上升( 0 ~ n 个)节点, 到达顶点, 后下降( 0 ~ n 个)节点。
我们可以通过枚举顶点的方式来枚举路径。
2. 我们枚举顶点时, 可以把路径分拆成3部分: 左侧路径、右侧路径和顶点。
如下面的路径, 顶点为 20, 左侧路径为 6 -> 15, 右侧为 6 -> 7。
-10
/ \
9 [20]
/ \
[15] [7]
/ / \
[6] 4 [6]
以当前节点为顶点的路径中, 最大和为 两侧路径的最大和 + 节点的值。
需要注意的是, 两侧路径也可能不选, 此时取 0。
3. 如何求两侧路径最大和? 看一个类似问题:求数组的最大子数组和。
动态规划: dp[i] 代表以 nums[i] 为结尾的子数组的最大和。
转移方程: dp[i] = max(dp[i-1], 0) + nums[i]。
4. 在树上, 设 dp[C] 代表以当前节点为结尾的最大上升路径和,
则我们需要对节点的左右子树做一个选择, 有
dp[C] = max(max(dp[L], 0), max(dp[R], 0)) + C.val
式中, C,L,R 分别代指 当前节点、左子节点、右子节点。
5. 最后, 以当前节点为顶点的路径中, 最大的和为
max(dp[L], 0) + max(dp[R], 0) + C.val。
我们枚举顶点, 并记录最大答案。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)