124. Binary Tree Maximum Path Sum
分からず答えみた
解法
再帰でやるよ
ある頂点と、そのサブツリー(左右とってもとらなくても良いとする)の最大値の和で最も大きいのが答えとなる
注意点
パスの定義
最初勘違いしてた。ひと繋ぎでできるやつ
以下みたいな感じ、ある頂点から左右に行くのはいいけど、それ以降の子ノードからは左右どちらかしか行ってはいけない
https://gyazo.com/5f116fa4fe4a4cf01f9d3186e941d852
再帰の返り値でなく、途中での最大値が解となる
再帰の返り値だと、root始まりの最大値しか求めれない。
再帰かつ、あるノードをrootとする場合の最大値を求める場合は、外にグローバル変数とか持たせておいて随時更新するしかない
コード
解説真似して書いたコード
グローバル変数定義版
code: solution1.go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var maxSum int
func maxPathSum(root *TreeNode) int {
// LeetCode用対応(テストケース間でグローバル変数が共有されるので、main内で初期値を代入し直す
maxSum = -math.MaxInt64
maxGain(root)
return maxSum
}
func maxGain(node *TreeNode) int {
if node == nil {
return 0
}
leftGain := max(maxGain(node.Left), 0)
rightGain := max(maxGain(node.Right), 0)
// このノードをrootととする最大値(ここは左と右を足す)
newPath := node.Val + leftGain + rightGain
maxSum = max(maxSum, newPath)
// 返り値では、右と左の大きい方のみを足す
return node.Val + max(leftGain, rightGain)
}
func max(a,b int) int {
if a <= b {
return b
} else {
return a
}
}
もう少し実用的にクロージャで表現した場合
code: solution.go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxPathSum(root *TreeNode) int {
maxSum := -math.MaxInt64
var maxGain func(*TreeNode) int
maxGain = func(node *TreeNode) int {
if node == nil {
return 0
}
leftGain := max(maxGain(node.Left), 0)
rightGain := max(maxGain(node.Right), 0)
newPath := node.Val + leftGain + rightGain
maxSum = max(maxSum, newPath)
return node.Val + max(leftGain,rightGain)
}
maxGain(root)
return maxSum
}
func max(a,b int) int {
if a <= b {
return b
} else {
return a
}
}