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 <unordered_map>
2#include <algorithm>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12class Solution {
13 unordered_map<TreeNode*, int> robMemo, notRobMemo;
14public:
15 int rob(TreeNode* root) {
16 return max(robHouse(root, true), robHouse(root, false));
17 }
18
19private:
20 int robHouse(TreeNode* node, bool canRob) {
21 if (!node) return 0;
22 if (canRob) {
23 if (robMemo.find(node) != robMemo.end()) return robMemo[node];
24 int rob = node->val + robHouse(node->left, false) + robHouse(node->right, false);
25 int notRob = robHouse(node->left, true) + robHouse(node->right, true);
26 robMemo[node] = max(rob, notRob);
27 return robMemo[node];
28 } else {
29 if (notRobMemo.find(node) != notRobMemo.end()) return notRobMemo[node];
30 int result = robHouse(node->left, true) + robHouse(node->right, true);
31 notRobMemo[node] = result;
32 return result;
33 }
34 }
35};This solution uses a recursive robHouse function with a canRob flag to indicate whether the current node can be robbed. It employs two hash maps to memoize results for nodes with and without robbing. The main rob method calls robHouse for both robbing and skipping the root node and returns the maximum.