Let's rob the Houses 🏠 | Simple and Easy Solution ✅✅ | Recursion + Memoization ✅
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves determining the maximum amount of money that can be robbed from a 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves determining the maximum amount of money that can be robbed from a binary tree of houses without robbing two directly connected houses. My initial thought is to use dynamic programming to track the maximum value that can be obtained at each node, considering two cases: robbing the current house or not robbing it.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Recursive Function with Memoization**: We define a recursive function `doingRobbery` that calculates the maximum amount of money that can be robbed starting from the current node (`curr`).\n   - If we rob the current node, we cannot rob its immediate children, so we consider the values of its grandchildren.\n   - If we do not rob the current node, we can choose to rob or not rob its immediate children, so we take the maximum value for each child.\n   - We store the results in a map (`ump`) to avoid redundant calculations (memoization).\n2. **Base Cases**: If the current node is `nullptr`, return 0. If the node has already been processed, return the stored result.\n3. **Rob or Not Rob**: For each node, calculate the maximum money that can be robbed by either robbing the current node or not robbing it. The final result is the maximum of these two values.\n4. **Main Function**: The `rob` function starts the process from the root node, using the helper function `doingRobbery` to determine the maximum amount that can be robbed.\n\n# Complexity\n- **Time complexity**: \n  - The time complexity is $$O(n)$$, where $$n$$ is the number of nodes in the tree. This is because each node is processed only once, and memoization ensures that we do not recompute the results for any node.\n\n- **Space complexity**: \n  - The space complexity is $$O(n)$$ due to the recursion stack and the unordered map used for memoization, where $$n$$ is the number of nodes in the tree.\n\n# Code\n```cpp []\nclass Solution {\n    int doingRobbery(TreeNode *curr, unordered_map<TreeNode *, int> &ump){\n        if(curr == nullptr) return 0;\n        if(ump.find(curr) != ump.end()) return ump[curr];\n\n        // Rob the current node\n        int robbed = curr->val + \n                     ((curr->left) ? (doingRobbery(curr->left->left, ump) + doingRobbery(curr->left->right, ump)) : 0) + \n                     ((curr->right) ? (doingRobbery(curr->right->left, ump) + doingRobbery(curr->right->right, ump)) : 0);\n\n        // Do not rob the current node\n        int notRobbed = doingRobbery(curr->left, ump) + doingRobbery(curr->right, ump);\n\n        // Store the result in the map and return the maximum of both scenarios\n        return ump[curr] = max(robbed, notRobbed);\n    }\n\npublic:\n    int rob(TreeNode* root) {\n        unordered_map<TreeNode *, int> ump;\n        return doingRobbery(root, ump);\n    }\n};\n```
['Dynamic Programming', 'Tree', 'Recursion', 'Memoization', 'C++']