leetcode124.二叉树中的最大路径和

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res int
func maxPathSum(root *TreeNode) int {
    if root==nil{
        return 0
    }
    if root.Left==nil && root.Right==nil{
        return root.Val
    }
    
    res=math.MinInt
    df(root)
    return res

}

func df(root *TreeNode) int{
    if root==nil{
        return 0
    }
    lMax:=max(0,df(root.Left))
    rMax:=max(0,df(root.Right))
    res=max(res,root.Val+lMax+rMax)
    return root.Val+max(lMax,rMax)
}

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