House Robber III

How it works

Instead of caching all nodes, we can return two values from each subtree: the maximum if we rob this node, and the maximum if we skip it. This eliminates the need for a hash map. For each node, "with root" equals the node value plus the "without" values of both children. "Without root" equals the sum of the maximum values (either with or without) from both children.

Steps

1. Define a recursive function that returns a pair: [maxWithNode, maxWithoutNode].
2. For a null node, return [0, 0].
3. Recursively get the pairs for left and right children.
4. Calculate withRoot as the node's value plus leftPair[1] plus rightPair[1] (children must be skipped).
5. Calculate withoutRoot as max(leftPair) plus max(rightPair) (children can be robbed or skipped).
6. Return [withRoot, withoutRoot].
7. The final answer is the maximum of the two values returned for the root.

Complexity

• Time complexity: O(n)
• Space complexity: O(n) for recursion stack.

Things to watch for

Confusing "Skip to Grandchildren" with "Must Rob Grandchildren"

When robbing the current node, you cannot rob its immediate children, so you recursively consider the grandchildren. However, a common mistake is thinking you must rob the grandchildren. In reality, for each grandchild, you still have the choice to rob it or skip it. The recursive call on grandchildren will make this decision optimally. The constraint only prevents robbing adjacent nodes (parent-child), not skipping multiple levels.

Not Handling Null Children Properly

When calculating the value of robbing the current node, you need to add values from grandchildren. If a child is null, accessing child.left or child.right will cause a null pointer error. Always check if the left or right child exists before attempting to access their children. A null child contributes 0 to the total, and its non-existent children also contribute 0.

Forgetting to Take Maximum in the Final Answer

The optimal DFS solution returns a pair [withRoot, withoutRoot] representing the maximum money if we rob or skip the current node. At the root level, the final answer is the maximum of these two values, not just one of them. Forgetting to take this maximum and returning only withRoot or withoutRoot will give an incorrect result whenever the optimal strategy at the root differs from what you returned.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: TreeNode) -> int:
        def dfs(root):
            if not root:
                return [0, 0]

            leftPair = dfs(root.left)
            rightPair = dfs(root.right)

            withRoot = root.val + leftPair[1] + rightPair[1]
            withoutRoot = max(leftPair) + max(rightPair)

            return [withRoot, withoutRoot]

        return max(dfs(root))

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        auto result = dfs(root);
        return max(result.first, result.second);
    }

private:
    pair<int, int> dfs(TreeNode* root) {
        if (!root) {
            return {0, 0};
        }

        auto leftPair = dfs(root->left);
        auto rightPair = dfs(root->right);

        int withRoot = root->val + leftPair.second + rightPair.second;
        int withoutRoot = max(leftPair.first, leftPair.second) +
                          max(rightPair.first, rightPair.second);

        return {withRoot, withoutRoot};
    }
};