Given a binary tree T, find the maximum path sum.
The path may start and end at any node in the tree.
Input Format:
The first and the only argument contains a pointer to the root of T, A.
Output Format:
Return an integer representing the maximum sum path.
Example :
Input 1:
1
/ \
2 3
Output 1:
6
Explanation 1:
The path with maximum sum is: 2 - 1 - 3
Input 2:
-10
/ \
-20 -30
Output 2:
-10
Explanation 2
The path with maximum sum is: -10
