337. House Robber III

The first way I tried intuitively is the recursive way.

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:  };