jaswanthi's blog

Recursion without using the static and global variables
By jaswanthi, 10 years ago, In English

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;
}
  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply