Maximum Path Sum in Binary Tree

meta 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: Input: -10 / \ 9 20 / \ 15 7 Output: 42 Constraints: The number of nodes in the tree is in the range [1, 3 * 10^4]. The value of a node in the tree is in the range [-1000, 1000]. Example Input -10 9 15 20 7