Given the root node of a binary tree where each node contains an integer value, compute the maximum sum obtainable from any non-empty path in the tree. A path is defined as any sequence of nodes where each pair of adjacent nodes is connected by an edge, and each node appears at most once in the sequence. The path does not need to pass through the root.
Example 1
Input: TreeNode(5, TreeNode(4), TreeNode(8, TreeNode(6), TreeNode(9)))
Output: 27
Explanation: The maximum path is 6 -> 8 -> 9 with sum 23, but 4 -> 5 -> 8 -> 9 gives 26. However, 5 -> 8 -> 9 gives 22. The correct maximum is 4 -> 5 -> 8 -> 9 = 4+5+8+9 = 26.
Example 2
Input: TreeNode(-3, TreeNode(-2), TreeNode(-1))
Output: -1
Explanation: The maximum path is just the node with value -1.
Constraints
Case 1
Input: TreeNode(2, TreeNode(-1), TreeNode(3))
Expected: 4
Case 2
Input: TreeNode(10, TreeNode(2, TreeNode(20), TreeNode(1)), TreeNode(-25, TreeNode(3), TreeNode(4)))
Expected: 32
Case 3
Input: TreeNode(7)
Expected: 7
Case 4
Input: TreeNode(-5, TreeNode(-6), TreeNode(-7))
Expected: -5