C++ DP solution with a vector to store two states
In this code, at every node, it returns a vector storing two states : rob this node or not rob\nres[0] means the max value I can get from the botton if I rob th
In this code, at every node, it returns a vector storing two states : rob this node or not rob\nres[0] means the max value I can get from the botton **if I rob this node**\nres[1] means the max value I can get from the botton **if I don\'t rob this node**\nTime O(n) the recu will visit every node\nSpace O(1n) every node takes O(1) space\n```\nclass Solution {\npublic:\n    int rob(TreeNode* root) {\n        if(!root) return 0;\n        vector<int> res = robHelper(root);\n        return max(res[0], res[1]);\n    }\n    vector<int> robHelper(TreeNode* root){\n        vector<int> res(2, 0);\n        if(!root) return res;\n        if(root->left == root->right){\n            res[0] = root->val;\n            return res;\n        } \n        vector<int> l = robHelper(root->left);\n        vector<int> r = robHelper(root->right);\n        res[0] = l[1] + r[1] + root->val;\n        res[1] = max(max(l[1] + r[1], l[0] + r[0]), max(l[1] + r[0], l[0] + r[1]));\n        return res;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']