Simple C++ DFS Solution
The general idea here is that at each node you have two choices. \nYou can either decide to rob that node, or skip it.\nFrom this central idea, we can derive th
The general idea here is that at each node you have two choices. \nYou can either decide to rob that node, or skip it.\nFrom this central idea, we can derive the following logic.\n\nAt each node, we return the possibilities if we had decided to rob that node, or if we had decided to skip it (this is represented in the structure RobbedRoot).\n\nTo find out the maximum stolen money if the robber had decided to steal from the current node, we must skip the left and right nodes.\n`int robThisNode = root->val + robLeft.skippedRoot + robRight.skippedRoot;`\nThis is so that we do not trip the alarms of two adjacent house nodes.\n\nHowever, if we decide to skip the current node, we have two options for the left and right sides.\nWe can now rob the left and/or right node, as our skipping of the current node means that we won\'t trip the alarm.\nBut we can also decide to skip the left and/or right node.\n\nThis is because greedily robbing the node just because you have the option to does not guarantee that you will make the maximum profit, as by robbing a node, you could block off an adjacent higher value node which could lead to a higher profit.\n\nFor example in:\n\n```cpp\n/*\n4\n    \\\n\t  1\n\t\t \\\n\t\t   2\n\t\t\t  \\\n\t\t\t\t3\n*/\n```\n\t\t\t\t\nDeciding to rob 2, after skipping 1, blocks off the more profitable 3.\nSo, we also need to take into account the cases for skipping the left and right nodes as well.\n\nHence:\n`int skipThisNode = max(robLeft.robbedRoot, robLeft.skippedRoot) + max(robRight.robbedRoot, robRight.skippedRoot);`\n\nHence, the final code:\n\n```cpp\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n * };\n */\n\nstruct RobbedRoot {\n    int robbedRoot;\n    int skippedRoot;\n};\n\nclass Solution {\nprivate:\n    RobbedRoot robDFS(TreeNode* root) {\n        if (root == nullptr) {\n            return RobbedRoot{0, 0};\n        }\n        \n        RobbedRoot robLeft = robDFS(root->left);\n        RobbedRoot robRight = robDFS(root->right);\n        \n        int robThisNode = root->val + robLeft.skippedRoot + robRight.skippedRoot;\n        int skipThisNode = max(robLeft.robbedRoot, robLeft.skippedRoot) + max(robRight.robbedRoot, robRight.skippedRoot);\n        \n        return RobbedRoot{robThisNode, skipThisNode};\n    }\npublic:\n    int rob(TreeNode* root) {\n        RobbedRoot finalState = robDFS(root);\n        \n        return max(finalState.robbedRoot, finalState.skippedRoot);\n    }\n};\n```
['C', 'C++']