HàPhan 河

Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

``````Input: [1,2,3]

1
/ \
2   3

Output: 6
``````

Example 2:

``````Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42
``````

Solution

There are FOUR type of sums that cross node
1: leftTree + node + rightTree
2: leftTree + node
3: node + rightTree
4: node
Just get max of those sums.

``````class Solution {
func maxPathSum(_ root: TreeNode?) -> Int {
var res = Int.min
maxUtil(root, &res)
return res
}

// 4 type of sum cross node
// 1: leftTree + node + rightTree
// 2: leftTree + node
// 3: node + rightTree
// 4: node
func maxUtil(_ node: TreeNode?, _ res: inout Int) -> Int{
guard let node = node else { return 0 }

let leftTree = maxUtil(node.left, &res)
let rightTree = maxUtil(node.right, &res)

let sumWithNodeAsLeaf = max(leftTree, rightTree) + node.val
let sumWithNodeAsRoot = leftTree + rightTree + node.val

let topMax = max(max(sumWithNodeAsLeaf, sumWithNodeAsRoot), node.val)

res = max(res, topMax)

return max(sumWithNodeAsLeaf, node.val)
}
}
``````