題目
二叉樹中的 路徑 被定義為一條節點序列，序列中每對相鄰節點之間都存在一條邊。同一個節點在一條路徑序列中 至多出現一次 。該路徑 至少包含一個 節點，且不一定經過根節點。
路徑和 是路徑中各節點值的總和。
給你一個二叉樹的根節點 root ，返回其 最大路徑和 。
示例
輸入：root = [-10,9,20,null,null,15,7]
輸出：42
解釋：最優路徑是 15 -> 20 -> 7 ，路徑和為 15 + 20 + 7 = 42
解析
func maxPathSum(root *TreeNode) int {ans := math.MinIntvar dfs func(*TreeNode) intdfs = func(node *TreeNode) int {if node == nil {return 0 // 沒有節點，和為0}leftMaxVal := dfs(node.Left) // 左子樹最大鏈和rightMaxVal := dfs(node.Right) // 右子樹最大鏈和ans = max(ans, leftMaxVal+rightMaxVal+node.Val) // 兩條鏈拼成路徑return max(max(leftMaxVal, rightMaxVal)+node.Val, 0) // 當前子樹最大鏈和}dfs(root)return ans
}
)
)
