Maximum Path Sum

Problem

Given the root of a 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.

Examples

// Tree structure:
//      1
//     /  \
//    2   3
maxPathSum([1,2,3])
// returns 6
// The max path is 2 -> 1 -> 3

// Tree structure:
//      -8
//     /    \
//    2    4
//         /   \
//       3     1
maxPathSum([-8,2,4,null,null,3,1])
// returns 8
// The max path is 3 -> 4 -> 1