0124-binary-tree-maximum-path-sum.swift

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * public var val: Int
 * public var left: TreeNode?
 * public var right: TreeNode?
 * public init() { self.val = 0; self.left = nil; self.right = nil; }
 * public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 * self.val = val
 * self.left = left
 * self.right = right
 * }
 * }
 */
classSolution{
varglobalMax:Int=Int.min

 // Return max path that '''ends at''' a particular node
privatefunc ends(at node:TreeNode?)->Int{
 // Base case
guardlet node = node else{return0}

 // Recursive cases
 // MAX with 0, to shorten negative paths
letleftMaxPath=max(ends(at: node.left),0)
letrightMaxPath=max(ends(at: node.right),0)

letpathIncludingNode= leftMaxPath + node.val + rightMaxPath
 globalMax =max(globalMax, pathIncludingNode)

letpathEndingAtNode=max(leftMaxPath, rightMaxPath)+ node.val
return pathEndingAtNode
}

func maxPathSum(_ root:TreeNode?)->Int{
ends(at: root)
return globalMax
}
}