Google Interview Question Java Developers
Country: United States
My idea is to keep track of max even sum and max odd sum of the paths going through a particular node. O(N) time, O(log N) space (in case of a balanced tree).
#include <iostream>
#include <vector>
using namespace std;
class Node {
public:
Node(int val)
{
val_ = val;
left_ = right_ = NULL;
}
int val_;
Node *left_, *right_;
};
class Sums {
public:
Sums(int even, int odd)
{
e_ = even;
o_ = odd;
}
int e_;
int o_;
};
Sums MaxSums(Node *n, int &max_e_sum)
{
Sums out(0, 0);
if (n) {
Sums l_max_sums = MaxSums(n->left_, max_e_sum);
Sums r_max_sums = MaxSums(n->right_, max_e_sum);
vector<int> sums = {
l_max_sums.e_ + n->val_,
l_max_sums.o_ + n->val_,
r_max_sums.e_ + n->val_,
r_max_sums.o_ + n->val_,
l_max_sums.e_ + r_max_sums.e_ + n->val_,
l_max_sums.e_ + r_max_sums.o_ + n->val_,
l_max_sums.o_ + r_max_sums.e_ + n->val_,
l_max_sums.o_ + r_max_sums.o_ + n->val_
};
for (int i = 0; i < 4; ++i) {
int sum = sums[i];
if (sum % 2 == 0) {
out.e_ = max(out.e_, sum);
max_e_sum = max(max_e_sum, out.e_);
} else {
out.o_ = max(out.o_, sum);
}
}
for (int i = 4; i < sums.size(); ++i) {
int sum = sums[i];
if (sum % 2 == 0) {
max_e_sum = max(max_e_sum, sum);
}
}
}
return out;
}
int main()
{
/*
10
/ \
2 5
/ \ \
1 101 13
*/
Node n10(10), n2(2), n5(5), n1(1), n101(101), n13(13);
n10.left_ = &n2;
n10.right_ = &n5;
n2.left_ = &n1;
n2.right_ = &n101;
n5.right_ = &n13;
int max_e_sum = 0;
MaxSums(&n10, max_e_sum);
cout << max_e_sum << "\n";
}
pair<int,int> maxarray(node * root, node * ref){
if(root==NULL) return pair<int,int>(0,0);
// general case
pair<int,int> fromleft = maxarray(root->left,ref) + root->value;
pair<int,int> fromright = maxarray(root->right,ref) + root->value;
int myself = root->value;
// root case
if(root==ref){
vector<int> ret;
ret.push_back(fromleft.first+fromright.first+root->value);
ret.push_back(fromleft.first+fromright.second+root->value);
ret.push_back(fromleft.second+fromright.first+root->value);
ret.push_back(fromleft.second+fromright.first+root->value);
return pair<int,int>(0,findmax(ret,1));
}
// find even most and odd most from these
vector<int> odds;
vector<int> evens;
hadder(odds,evens,fromleft);
hadder(odds,evens,fromright);
hadder(odds,evens,myself);
return pair<int,int>(findmax(odds,0),findmax(evens,0));
}
int max =0;
private static int[] maximumEvenSum(TreeNode node){
if(node == null)
return new int[]{0, 0};
if(node.left == null && node.right == null){
if(node.val % 2 == 0){
max = Math.max(max, node.val);
return new int[]{0, node.val};
} else{
return new int[]{node.val, 0};
}
}
int[] left = maximumEvenSum(node.left);
int[] right = maximumEvenSum(node.right);
int even = 0;
int odd = 0;
if(node.val % 2 == 0){
even = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val);
odd = Math.max(Math.max(left[0] + node.val, right[0] + node.val) , 0);
if(even%2 == 0)
max = Math.max(even, max);
if((left[0] + node.val + right[0]) % 2 == 0)
max = Math.max(left[0] + node.val + right[0], max);
if((left[1] + node.val + right[1]) % 2 == 0)
max = Math.max(left[1] + node.val + right[1], max);
} else{
even = Math.max(Math.max(left[0] + node.val, right[0] + node.val), 0);
odd = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val);
if(even%2 == 0)
max = Math.max(even, max);
if((left[0] + node.val + right[1]) % 2 == 0)
max = Math.max(left[0] + node.val + right[1], max);
if((left[1] + node.val + right[0]) % 2 == 0)
max = Math.max(left[1] + node.val + right[0], max);
}
left[1] = even;
left[0] = odd;
return left;
}
It should be post order traversal with below way of cal
If leaf
=>Item: odd
. Return ( 0, value)
=> item : even
. Return ( value, 0)
If not leaf
=> item even
// through both child's creating max subtree
. max = MAX ( max, MAX(left.even+ right.even, left.odd+ right.odd) + value)
return (
even-> MAX ( MAX ( left.even, right.even) + value, value),
odd ->( left.odd, right.odd) + value )
)
=> item odd
// through both child's creating max subtree
. max = MAX ( max, left.odd + right.odd + value)
return (
even-> ( left.odd, right.odd) + value),
odd -> MAX ( left.even, right.eve) + value, value )
)
if any situation the value at odd position is even, then put 0 instead
Like tree
6 here even sum is not possible (6+2 = even, 6+4= even, 2+4+6 = even) not possible odd sum( 10,0)
2 4
Same for even.
- Popeye July 20, 2018int max =0; private static int[] maximumEvenSum(TreeNode node){ if(node == null) return new int[]{0, 0}; if(node.left == null && node.right == null){ if(node.val % 2 == 0){ max = Math.max(max, node.val); return new int[]{0, node.val}; } else{ return new int[]{node.val, 0}; } } int[] left = maximumEvenSum(node.left); int[] right = maximumEvenSum(node.right); int even = 0; int odd = 0; if(node.val % 2 == 0){ even = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val); odd = Math.max(Math.max(left[0] + node.val, right[0] + node.val) , 0); if(even%2 == 0) max = Math.max(even, max); if((left[0] + node.val + right[0]) % 2 == 0) max = Math.max(left[0] + node.val + right[0], max); if((left[1] + node.val + right[1]) % 2 == 0) max = Math.max(left[1] + node.val + right[1], max); } else{ even = Math.max(Math.max(left[0] + node.val, right[0] + node.val), 0); odd = Math.max(Math.max(left[1] + node.val, right[1] + node.val) , node.val); if(even%2 == 0) max = Math.max(even, max); if((left[0] + node.val + right[1]) % 2 == 0) max = Math.max(left[0] + node.val + right[1], max); if((left[1] + node.val + right[0]) % 2 == 0) max = Math.max(left[1] + node.val + right[0], max); } left[1] = even; left[0] = odd; return left; }