C++ DP
This is a straightforwad DP problem. \nThe helper function returns a pair of {the best result of the subtree if root is robbed, the best result of the subtree i
This is a straightforwad DP problem. \nThe `helper` function returns a pair of `{the best result of the subtree if root is robbed, the best result of the subtree if root is not robbed}`.\n\nTime complexity `O(n)`\nSpace complexity `O(n)` (considering the call stack)\n\n```\n    pair<int, int> helper(TreeNode* root)\n    {\n        if (!root)\n            return {0, 0};\n        auto l = helper(root->left);\n        auto r = helper(root->right);\n        int cur_not_rob = max(l.first, l.second) + max(r.first, r.second);\n        int cur_rob = l.second + r.second + root->val;\n        return {cur_rob, cur_not_rob};\n    }\n    \n    int rob(TreeNode* root) {\n        auto res = helper(root);\n        return max(res.first, res.second);\n    }\n```
['Dynamic Programming', 'Tree', 'C']