标签:最大路 题目 bool 左右子树 必须 sum lex 思路 str
题目描述
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
输入:[1,2,3]
1
/ 2 3
输出:6
示例 2:
输入:[-10,9,20,null,null,15,7]
-10
/ 9 20
/ 15 7
输出:42
算法
在本题中采用了递归的方法,思路就是遍历每一个结点,然后取得最大值,设结点node
,它的左子树的最大值为lNode
,它的右子树的最大值为rNode
,那么对于结点node
的最大路径和为:
max(node.Val,node.Val+lNode,node.Val+rNode,node.Val+lNode+rNode,lNode,rNode)
,就是获取他们中的最大值
但是我们在求结点node
的子树的最大值的时候,需要注意一下几个方面
- 必须包含子树的根结点的值
- 必须只能包含子树的一边子树,而不能同时包含左右子树
算法步骤如下:
- 首先定义递归函数的全局变量
res=node.Val
- 然后定义递归函数,参数就是一个结点
node
- 如果
res<node.Val
,就将node.Val
的结果赋值给res
- 如果
node
的左子树存在,调用递归函数,传入node.Left
,得到结果lNode
- 如果
res<node.Val+lNode
,那么res=node.Val+lNode
- 如果
res<lNode
,那么res=lNode
- 如果
- 如果
node
的右子树存在,调用递归函数,传入node.Right
,得到结果rNode
- 如果
res<node.Val+rNode
,那么res=node.Val+rNode
- 如果
res<rNode
,那么res=rNode
- 如果
- 当左右子树同时存在的时候,还要比较
res<node.Val+lNode+rNode
- 递归函数的返回值为
max(node.Val,node.Val+lNode,node.Val+rNode)
- 如果
代码
func maxPathSum(root *TreeNode) int {
if root == nil {
return 0
}
res := root.Val
var findMax func(node *TreeNode) int
findMax = func(node *TreeNode) int {
var lExist, rExist bool
var Lroot, Rroot int
tmpMax := node.Val
if res < node.Val {
res = node.Val
}
if node.Left != nil {
lExist = true
Lroot = findMax(node.Left)
if res < node.Val+Lroot {
res = node.Val + Lroot
}
if res < Lroot {
res = Lroot
}
if tmpMax < node.Val+Lroot {
tmpMax = node.Val + Lroot
}
}
if node.Right != nil {
rExist = true
Rroot = findMax(node.Right)
if res < node.Val+Rroot {
res = node.Val + Rroot
}
if res < Rroot {
res = Rroot
}
if tmpMax < node.Val+Rroot {
tmpMax = node.Val + Rroot
}
}
if lExist && rExist {
// 同时存在左子树和右子树
if res < node.Val+Lroot+Rroot {
res = node.Val + Lroot + Rroot
}
}
return tmpMax
}
_ = findMax(root)
return res
}
leetcode之124二叉树中的最大路径和Golang
标签:最大路 题目 bool 左右子树 必须 sum lex 思路 str
原文地址:https://www.cnblogs.com/gyyyl/p/14166814.html
暂无评论...