I came up a solution for the following problem.
But, I want to do it in true recursive way. Can you help with coming up with Pair<int,int> or Object.
Problem:
Given a binary tree, find the maximum path sum. It can contain -ve values
The path may start and end at any node in the tree. For example: Given the below binary tree,
1
/ \
2 3
Return 6.
Given the below binary tree,
-2
\
-1
Return -1.
Solution with Global variable way:
int max = Integer.MIN_VALUE
public int calculateSum(TreeNode root) {
if (root == null)
return 0;
int left = calculateSum(root.left, max);
int right = calculateSum(root.right, max);
int current = Math.max(root.val, Math.max(root.val + left, root.val + right));
max = Math.max(max, Math.max(current, left + root.val + right));
return current;
}
You can return pair<max sum, head of list representing the best way>. So you can choose pair with greater sum, and add current node to list in O(1).
Wow, I thought the task is to find the best descending path in binary tree.
Am I the only one who can't see no global variables here? Could you describe a problem a bit carefully — what do you want?