Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum. The path is defined as any sequence of nodes starting from some node and ending at 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. For example, given the following binary tree: 1 / \ 2 3 Return the maximum path sum which is 6. Input/Output Specification Input: Root node of a binary tree (TreeNode type) Output: Integer, representing the maximum path sum. Examples Input: [1, 2, 3] Output: 6 Input: [-10, 9, 20, null, null, 15, 7] Output: 42. Assume the range of node values is [-1000, 1000] and the number of nodes does not exceed 3000. Example Input [1, 2, 3]