leetCodeTreeHard.swift

// https://leetcode.com/problems/binary-tree-maximum-path-sum/
// O(n), Space O(n)
var globalMax = Int.min
func maxPathSum(_ root: TreeNode?) -> Int {
    maxPath(root)
    return globalMax
}

func maxPath(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }
    let currVal = root.val
    let left = max(0, maxPath(root.left))
    let right = max(0, maxPath(root.right))
    globalMax = max(globalMax, left + currVal + right)
    return max(left, right) + currVal
}