题解 | #二叉树的最大路径和#

package main
import "math"
import . "nc_tools"

func maxPathSum( root *TreeNode ) int {
    maxSum := math.MinInt32

    var dfs func(root *TreeNode) int
    dfs = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        left := dfs(root.Left)
        right := dfs(root.Right)

        input_maxSum := left + root.Val + right
        maxSum = max(maxSum, input_maxSum)
        output_maxSum := max(left, right) + root.Val

        return max(output_maxSum, 0)
    }
    dfs(root)
    return maxSum
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}