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

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

var sum = Int.min

func maxPathSum(_ root: TreeNode?) -> Int {
    value(root)
    return sum
}
//思路： 后序遍历
func value(_ node: TreeNode?) -> Int{
    if node == nil {return 0}
   
    let leftValue = max(value(node?.left), 0)
    let rightValue = max(value(node?.right), 0)
    //获取经过的路线最大的sum
    sum = max(sum, node!.val + leftValue + rightValue)
    //获取单个节点能提供和的最大值
    return node!.val + max(leftValue, rightValue)
}