LeetCode Q124: Binary Tree Maximum Path Sum (hard)

Given 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 does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Solution:

Using recursion and compute the maximum path under each node. For each node return the current maximum path passing the node.