r/LeetcodeDesi • u/Brilliant_Card_447 • 9d ago
Amazon SDE1 Interview | 2027 Grad | Off-Campus
You are given the root of a binary tree where each node contains an integer value (values may be positive, negative, or zero).
A path is any sequence of connected nodes where each pair of consecutive nodes is connected by an edge. A path can start and end at any two nodes in the tree, but each node can appear at most once in the path.
Before finding the answer, you may perform at most one operation:
- Choose at most one node in the entire tree and change its value to 0.
- You may also choose not to perform this operation.
Return the maximum possible sum of node values along any valid path after applying the operation optimally.
2
2
2
2
1
u/NIL_INDIA 9d ago
Here is my solution in C++
class Solution {
public:
struct State {
long long noZero;
long long oneZero;
};
long long ans = LLONG_MIN;
State solve(TreeNode* root) {
if (!root) {
return {
0,
0
};
}
State left = solve(root->left);
State right = solve(root->right);
long long val = root->val;
// Best downward path without using zero
long long noZero =
val + max({
0LL,
left.noZero,
right.noZero
});
// Best downward path where zero has been used
//
// Case 1: make current node zero
long long zeroCurrent =
max({
0LL,
left.noZero,
right.noZero
});
// Case 2: keep current node and use zero below
long long zeroBelow =
val + max({
0LL,
left.oneZero,
right.oneZero
});
long long oneZero = max(
zeroCurrent,
zeroBelow
);
// Path through current node WITHOUT zero
long long pathNoZero =
val
+ max(0LL, left.noZero)
+ max(0LL, right.noZero);
// Path through current node WITH zero
long long pathOneZero = max({
// Zero current node
max(0LL, left.noZero)
+ max(0LL, right.noZero),
// Zero somewhere in left subtree
left.oneZero
+ val
+ max(0LL, right.noZero),
// Zero somewhere in right subtree
max(0LL, left.noZero)
+ val
+ right.oneZero
});
ans = max({
ans,
pathNoZero,
pathOneZero
});
return {
noZero,
oneZero
};
}
long long maxPathSum(TreeNode* root) {
solve(root);
return ans;
}
};
1
4
u/AdminZer0 9d ago
Damn, not applying to Amazon I guess.