二叉樹中的最大路徑和
這題思考的時(shí)候還是比較簡(jiǎn)單的豺总，首先思考的最大路徑和的計(jì)算邏輯麸恍，同樣使用的是遞歸
結(jié)束邏輯：出現(xiàn)空節(jié)點(diǎn)的時(shí)候
計(jì)算邏輯：計(jì)算根節(jié)點(diǎn)和左右子節(jié)點(diǎn)之和根節(jié)點(diǎn)與左右較大節(jié)點(diǎn)的比較，返回當(dāng)前較大值，累計(jì)最大值
可以通過遞歸的計(jì)算的節(jié)點(diǎn)健蕊，都是只能和左右節(jié)點(diǎn)中其中一個(gè)來計(jì)算的
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxPathSum(root *TreeNode) int {
_,maxSum:= helper(root)
return maxSum
}
func helper(root *TreeNode)(int,int){
if root == nil{
return 0,math.MinInt32
}
leftVal,leftMax := helper(root.Left)
leftVal = max(leftVal,0)
rightVal,rightMax := helper(root.Right)
rightVal = max(rightVal,0)
newSum := root.Val + leftVal + rightVal
return root.Val + max(leftVal,rightVal), max(max(leftMax,rightMax),newSum)
}
func max (left,right int)int{
if left > right {
return left
}
return right
}
路徑總和 II
這題的思路還是很清晰的，在通過簡(jiǎn)單的題目之后乳蓄，這題就顯得很容易，唯一需要處理的就是怎么將所有路徑返回
出現(xiàn)了這幾個(gè)問題：
1夕膀、不能使用全局變量：這里之前對(duì)結(jié)果使用全局變量虚倒，但是代碼執(zhí)行的邏輯，意味著結(jié)果會(huì)出現(xiàn)重復(fù)的問題
2产舞、golang中出現(xiàn)的在二維切片中魂奥，添加切片的問題
ret = append(ret,append([]int{},singleRet...))
最終結(jié)果是這樣的
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) [][]int {
var(
ret [][]int
singleRet []int
)
var h func(root*TreeNode,targetSum int)
h = func(root*TreeNode,targetSum int){
if root == nil{
return
}
targetSum -=root.Val
singleRet = append(singleRet,root.Val)
defer func() {
singleRet = singleRet[:len(singleRet)-1]
}()
if root.Left == nil && root.Right ==nil && targetSum == 0{
ret = append(ret,append([]int{},singleRet...))
}
h(root.Left,targetSum)
h(root.Right,targetSum)
}
h(root,targetSum)
return ret
}
