1: class Solution {
2: public:
3: int rob(TreeNode* root) {
4: if (root == NULL) return 0;
5: int val = root->val;
6: if (root->left != NULL) {
7: val += rob(root->left->left) + rob(root->left->right);
8: }
9: if (root->right != NULL) {
10: val += rob(root->right->left) + rob(root->right->right);
11: }
12: int ret = max(val, rob(root->left)+rob(root->right));
13: return ret;
14: }
15: };
However, this solution hits TLE. By looking into the solution, you'll see that for each root, we'll compute root->left->left once but we'll compute it in rob(root->left) again. So there is overlapped subproblems. To reduce the overlapping, we can memorize the subproblems' result. So the problem becomes DP.
1: class Solution {
2: private:
3: unordered_map<TreeNode*, int> map;
4: public:
5: int rob(TreeNode* root) {
6: if (root == NULL) return 0;
7: if (map.find(root) != map.end()) return map[root];
8: int val = root->val;
9: if (root->left != NULL) {
10: val += rob(root->left->left) + rob(root->left->right);
11: }
12: if (root->right != NULL) {
13: val += rob(root->right->left) + rob(root->right->right);
14: }
15: int ret = max(val, rob(root->left)+rob(root->right));
16: map[root] = ret;
17: return ret;
18: }
19: };
No comments:
Post a Comment