Very Simple and Intuitive C++ Dp solution
We basically have two cases:\n1. Take the root\n2. Don\'t take the root\n\nFor CASE I, we take the root and all the left and right children of root->left and ro
We basically have two cases:\n**1. Take the root\n2. Don\'t take the root**\n\nFor **CASE I**, we take the root and all the left and right children of root->left and root->right i.e.,\nresult = root+(root->left->left)+(root->left->right)+(root->right->left)+(root->right->right)\n**Note**: We can\'t take (root->left) and (root->right) if we take the root node\n\nFor **CASE II**, we can break it into two sub cases:\ni) Take root->left\nii) Take root->right\n\nFor CASE i) we take (root->left) + max ((root->right), (root->right->left)+(root->right->right))\nFor CASE ii) we take (root->right) + max ((root->left), (root->left->left)+(root->left->right))\n\nAt the end, we take max of all these results and return it\n\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    unordered_map<TreeNode*,int>mp;\n    int solve(TreeNode* root){\n        //base case\n        if(!root)return 0;\n        if(mp.count(root))return mp[root];\n        int l=solve(root->left);\n        int r=solve(root->right);\n        int ll=0,lr=0,rl=0,rr=0;\n        if(root->left){\n            ll=solve(root->left->left);\n            lr=solve(root->left->right);\n        }\n        if(root->right){\n            rl=solve(root->right->left);\n            rr=solve(root->right->right);\n        }\n        int val=root->val;\n        int lmx=ll+lr;\n        int rmx=rl+rr;\n        //if we take the root node\n        int t1=val+lmx+rmx;\n        //if we take the left child of root\n        int t2=l+max(r,rmx);\n        //if we take the right child of root\n        int t3=r+max(l,lmx);\n        //take maximum of all the cases and memoize\n        mp[root]=max(t1,max(t2,t3));\n        return mp[root];\n    }\n    int rob(TreeNode* root) {\n        return solve(root);\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Memoization', 'C']