Simple C++ solution | DP | recursion | Memoization
Intuition\nAs we need to find the maximum sum of the nodes of the tree which are not directly linked, we can use a DFS traversal. And if we decide to pick a nod
# Intuition\nAs we need to find the maximum sum of the nodes of the tree which are not directly linked, we can use a DFS traversal. And if we decide to pick a node, then we will have to skip its child nodes and consider the grandchild nodes. If we decide not to pick a node, then we can pick its child nodes.\n\n# Approach\n1. For every recursive call, check the following\n2. If the node does not exist, return 0.\n3. If we have already calculated the amount if we decide to pick up a node, return the value from the map.\n4. For the 1st scenario of picking the node, add the node value to a variable called pick. If its grandchildren exist, then recursively call the function for them and add the value to pick variable.\n5. For the 2nd scenario of not picking the current node, set a variable not_pick to 0. If its child nodes exist, then recursively call the function for them and add the value to not_pick variable.\n6. return the max of pick and not_pick. And also update the map of current node with the max.\n\n# Complexity\n\n### Time complexity\nO(n)\n\n### Space complexity\nO(n)\n\n\n# Code\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\n    int solve(TreeNode* node,unordered_map<TreeNode*,int>& dp){\n        if(!node){return 0;}\n        int pick = node->val;\n        if(dp.find(node)!=dp.end()){return dp[node];}\n        if(node->left && node->left->left){pick+=solve(node->left->left,dp);}\n        if(node->left && node->left->right){pick+=solve(node->left->right,dp);}\n        if(node->right && node->right->left){pick+=solve(node->right->left,dp);}\n        if(node->right && node->right->right){pick+=solve(node->right->right,dp);}\n        int not_pick = 0;\n        if(node->left){not_pick+=solve(node->left,dp);}\n        if(node->right){not_pick+=solve(node->right,dp);}\n        return dp[node]=max(pick,not_pick);\n    }\n\n    int rob(TreeNode* root) {\n        unordered_map<TreeNode*,int> dp;\n        return solve(root,dp);\n    }\n};\n```
['Dynamic Programming', 'Tree', 'Depth-First Search', 'Memoization', 'Binary Tree', 'C++']