Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum. A path is defined as a sequence of nodes connected by parent-child connections in the tree. The path sum is the sum of node values in a path. The number of nodes in the tree is in the range [0, 10^4], and each node's value is in the range [-1000, 1000]. Example Input 2 1 -2 3