[C++] DFS/DP Recursive Memoised Solution Explained, ~85% Time, ~40% Space
Neat one that had me think for a moment and try a wrong approach first (see last bit of the code); then I opted to go for a simpler solution and I solved it in 
Neat one that had me think for a moment and try a wrong approach first (see last bit of the code); then I opted to go for a simpler solution and I solved it in one line.\n\nAt each iteration, we will first of all check if we have `root` and:\n* if not, we of course return `0`;\n* if yes, then we compute the max between:\n\t* the current value (`root->val`) + the recursive calls to `rob` passing each of its grandchildren (if any, `0` otherwise);\n\t* the sum of the recursive calls to `rob` passing it its direct children `root->left` and `root->right` (again if any, `0` otherwise).\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    int rob(TreeNode* root) {\n        return root ? max(root->val + (root->left ? rob(root->left->left) + rob(root->left->right) : 0) + (root->right ? rob(root->right->left) + rob(root->right->right) : 0), rob(root->left) + rob(root->right)) : 0;\n    }\n};\n```\n\nSame code, expanded on more lines for better readability:\n\n```cpp\nclass Solution {\npublic:\n    int rob(TreeNode* root) {\n        return root ? max(\n            // current value plus values of the grandchildren (if any, 0 otherwise)\n            root->val\n            + (root->left ? rob(root->left->left) + rob(root->left->right) : 0)\n            + (root->right ? rob(root->right->left) + rob(root->right->right) : 0),\n            // values of the direct children (if any, 0 otherwise)\n            rob(root->left) + rob(root->right)\n        ) : 0;\n    }\n};\n```\n\nWhich times out, so memoisation time it is - same logic, but wrapped through a helper function that checks if we already had a result computed in the hashmap `memo` for that specific node - if so we return it, if not we compute and store it:\n\n```cpp\nclass Solution {\npublic:\n    unordered_map<TreeNode*, int> memo;\n    int memoisedRob(TreeNode* root) {\n        return memo.find(root) != end(memo) ? memo[root] : memo[root] = rob(root);\n    }\n    int rob(TreeNode* root) {\n        return root ? max(root->val + (root->left ? memoisedRob(root->left->left) + memoisedRob(root->left->right) : 0) + (root->right ? memoisedRob(root->right->left) + memoisedRob(root->right->right) : 0), memoisedRob(root->left) + memoisedRob(root->right)) : 0;\n    }\n};\n```\n\nAnd just for the chronicles, my first BFS-based attempt, making the wrong assumption that proceeding by layers and applying the formula from the other problems was what was needed to solve this problem - regrettably it works only with very short trees:\n\n```cpp\nclass Solution {\npublic:\n    int rob(TreeNode* root) {\n        // aufwiedersehen, edge case\n        if (!root) return 0;\n        // support variables\n        vector<int> houseRows;\n        int len = 1, dp[3];\n        TreeNode *curr;\n        queue<TreeNode*> q;\n        q.push(root);\n        // BFSing our way into getting the cumulative values of each row\n        while (len) {\n            houseRows.push_back(0);\n            while (len--) {\n                // extracting the front of the queue\n                curr = q.front();\n                q.pop();\n                // increasing the matching row in houseRows\n                houseRows.back() += curr->val;\n                // adding possible children to q\n                if (curr->left) q.push(curr->left);\n                if (curr->right) q.push(curr->right);\n            }\n            len = q.size();\n        }\n        // recycling len - bad practice in production and interviews, but we are stingy here\n        len = houseRows.size();\n        dp[0] = houseRows[0];\n        dp[1] = max(houseRows[0], houseRows[1]);\n        dp[2] = max(houseRows[2] + dp[0], dp[1]);\n        for (int n: dp) cout << n << \' \';\n        for (int i = 3; i < len; i++) {\n            dp[i % 3] = max(dp[(i - 1) % 3], max(dp[(i - 3) % 3], dp[(i - 2) % 3]) + houseRows[i]);\n        }\n        return dp[--len % 3];\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Recursion', 'Memoization', 'C', 'C++']