Sponsored
Sponsored
This approach uses recursion along with memoization to store the maximum robbery amount for each node of the tree. The idea is to leverage a helper function that returns two values for each node: maximum money if the current node is included and maximum money if the current node is not included. At each node, we have two choices: either rob this node or not rob it, and for each choice, there are further choices for child nodes and so on.
Time Complexity: O(N), where N is the number of nodes in the tree, as each node is visited only once. Space Complexity: O(N) due to the recursion stack space in the worst case of a skewed tree.
1#include <stdlib.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode *right;
7};
8
9struct Robbery {
10 int withRob;
11 int withoutRob;
12};
13
14struct Robbery helper(struct TreeNode* node) {
15 if (!node) {
16 struct Robbery empty = {0, 0};
17 return empty;
18 }
19
20 struct Robbery left = helper(node->left);
21 struct Robbery right = helper(node->right);
22
23 struct Robbery current;
24 current.withRob = node->val + left.withoutRob + right.withoutRob;
25 current.withoutRob = (left.withRob > left.withoutRob ? left.withRob : left.withoutRob) +
26 (right.withRob > right.withoutRob ? right.withRob : right.withoutRob);
27
28 return current;
29}
30
31int rob(struct TreeNode* root) {
32 struct Robbery result = helper(root);
33 return result.withRob > result.withoutRob ? result.withRob : result.withoutRob;
34}The C solution adapts the recursive strategy. It defines a structure to return both robbery options, with and without robbing, for each node. This leverages recursion to aggregate node values from leaf nodes to the root.