c++ faster 100% space 100%
we define function rob return the maximum amount of money.\nAnd It will automatically contact the police if two directly-linked houses were broken into on the s
we define function rob return the maximum amount of money.\n**And It will automatically contact the police if two directly-linked houses were broken into on the same night.**\n\nit means that if we choose the value of current node we cannot choose the value of beside node.\nso the ans = max(current->val + (**the largest amount of money without choosing the beside node**), **the largest amount of money without choosing the current node**);\n\nhow can we find the **the largest amount of money without choosing the beside node**?\nfor example, if the current node is the root,\n**the largest amount of money without choosing the beside node** = rob(current->left->left) + rob(current->left->right) + rob(current->right->left) + rob(current->right->right)\n= 3 + 1 = 4.\n\n**how can we simplify it?**\nwhen backtracking, we can use variable sum to store the sum of rob(current->left) and rob(current->right).\nand when it backtrack to the parent node, current = parent node. \nAnd sum = (rob(current->left->left) + rob(current->left->right)) \nor (rob(current->left->left) + rob(current->left->right)).\n\nso when it backtrack to the parent node, we use preSum to store **the largest amount of money without choosing the beside node**.\nAnd the end we return max(root->val + preSum, sum).\n![image](https://assets.leetcode.com/users/images/47b68fc3-a39d-49b2-8ca5-6908125a36ce_1653318138.3652587.png)\n\n```\nclass Solution {\npublic:\n    int sum = 0;\n    int rob(TreeNode* root) {\n        if(!root){\n            sum = 0;\n            return 0;\n        }\n        int l = rob(root->left);\n        int preSum = sum;\n        int r = rob(root->right);\n        preSum += sum;\n        sum = l + r;\n        return max(root->val + preSum, sum);\n    }\n};\n```
['Dynamic Programming', 'C']