337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

Output: 7 
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

概念上就是要如果該level已經rob了，那就要隔一層之後才能繼續rob。一般DFS會有很多重複計算的部分，用hashmap來做memoization。helper function裡的val是rob該node的結果，helper(root->left, memo) + helper(root->right, memo)是不rob該node的結果。

// DFS + Memoization
int rob(TreeNode* root) { // time: O(n); space: O(n)
    unordered_map<TreeNode*, int> memo;
    return helper(root, memo);
}
int helper(TreeNode* root, unordered_map<TreeNode*, int>& memo) {
    if (!root) return 0;
    if (memo.count(root)) return memo[root];
    int val = root->val; // rob the current tree node
    if (root->left) {
        val += helper(root->left->left, memo) + helper(root->left->right, memo);
    }
    if (root->right) {
        val += helper(root->right->left, memo) + helper(root->right->right, memo);
    }
    return memo[root] = max(val, helper(root->left, memo) + helper(root->right, memo));
}