C++ implementation refer to @fun4LeetCode
First naive Solution \n\n    class Solution {\n    public:\n        int rob(TreeNode root) {\n            if(root == NULL)  return 0;\n            int val = 0;\
First naive Solution \n\n    class Solution {\n    public:\n        int rob(TreeNode* root) {\n            if(root == NULL)  return 0;\n            int val = 0;\n            if(root->left) {\n                val += rob(root->left->left) + rob(root->left->right);\n            }\n            if(root->right) {\n                val += rob(root->right->left) + rob(root->right->right);\n            }\n            return max(val + root->val, rob(root->left) + rob(root->right));\n        }\n    };\n\nSecond, use the dict to record the sub-problem information method\n\n    class Solution {\n    public:\n        int rob(TreeNode* root) {\n            unordered_map<TreeNode*, int> dict;\n            return help(root, dict);\n        }\n        \n        int help(TreeNode* root, unordered_map<TreeNode*, int>& dict) {\n            if(root == NULL)  return 0;\n            if(dict.find(root)!=dict.end())  return dict[root];\n            int val = 0;\n            if(root->left != NULL) {\n                val += help(root->left->left, dict) + help(root->left->right, dict);\n            }\n            if(root->right != NULL) {\n                val += help(root->right->left, dict) + help(root->right->right, dict);\n            }\n            val = max(val + root->val, help(root->left, dict) + help(root->right, dict));\n            dict[root] = val;\n            return val;\n        }\n    };\n\nThird Solution  is optimized a bit :\n\n    class Solution {\n    public:\n        int rob(TreeNode* root) {\n            vector<int> result = help(root);\n            return max(result[0], result[1]);\n        }\n        /**\n         * result[0] : record the max sum exclude the root value\n         * result[1] : record the max sum include the root value\n         **/\n        vector<int> help(TreeNode* root) {\n            vector<int> result(2, 0);\n            if(!root) {\n                return result;\n            }\n            vector<int> left = help(root->left);\n            vector<int> right = help(root->right);\n            /** root excluded : so we can include the child or not **/\n            result[0] = max(left[0], left[1]) + max(right[0], right[1]);\n            /** root included : so must exclude the child **/\n            result[1] = root->val + left[0] + right[0];\n            return result;\n        }\n    };
[]