House Robber III

Problem Description

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called 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 form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Examples

Constraints

• The number of nodes in the tree is in the range [1, 10⁴].
• 0 <= Node.val <= 10⁴

Tree DP (Rob or Don’t Rob)

This is a dynamic programming problem on trees. For any node, we must make a binary choice: either we rob it, or we do not rob it. We define a helper function robSub(node) that returns a pair/array containing:

• result[0]: The maximum money if we do not rob the current node.
• result[1]: The maximum money if we do rob the current node. For any node:

1. If the node is null, return [0, 0].
2. Recursively solve for its left child (left = robSub(node.left)) and right child (right = robSub(node.right)).
3. If we do not rob the current node, we can choose to rob or not rob its children (we take the maximum of each child’s state): rob_none = max(left[0], left[1]) + max(right[0], right[1]).
4. If we do rob the current node, we cannot rob its children. We must take their “do not rob” results: rob_this = node.val + left[0] + right[0].
5. Return [rob_none, rob_this]. The root answer is max(result[0], result[1]).

Solution 1: Dynamic Programming on Trees (Postorder)

Calculate rob/skip options bottom-up to build optimal tree decision values.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    public int rob(TreeNode root) {
        int[] result = robSub(root);
        return Math.max(result[0], result[1]);
    }

    private int[] robSub(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0}; // [skipped, robbed]
        }

        int[] left = robSub(node.left);
        int[] right = robSub(node.right);

        // If we do not rob this house, we can choose to rob or skip left/right children
        int skipThis = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        // If we rob this house, we must skip both left and right children
        int robThis = node.val + left[0] + right[0];

        return new int[]{skipThis, robThis};
    }
}

# 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: Optional[TreeNode]) -> int:
        
        def rob_sub(node: Optional[TreeNode]) -> tuple[int, int]:
            if not node:
                return (0, 0)  # (skipped, robbed)
                
            left = rob_sub(node.left)
            right = rob_sub(node.right)
            
            # If we skip this house, we take the max possible from children
            skip_this = max(left[0], left[1]) + max(right[0], right[1])
            
            # If we rob this house, we must skip children
            rob_this = node.val + left[0] + right[0]
            
            return (skip_this, rob_this)

        result = rob_sub(root)
        return max(result[0], result[1])

#include <algorithm>
#include <utility>

/**
 * 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 {
private:
    std::pair<int, int> robSub(TreeNode* node) {
        if (!node) return {0, 0};

        auto left = robSub(node->left);
        auto right = robSub(node->right);

        int skipThis = std::max(left.first, left.second) + std::max(right.first, right.second);
        int robThis = node->val + left.first + right.first;

        return {skipThis, robThis};
    }

public:
    int rob(TreeNode* root) {
        auto result = robSub(root);
        return std::max(result.first, result.second);
    }
};

Complexity Analysis

• Time Complexity: O(n) since we visit every node in the binary tree exactly once.
• Space Complexity: O(h) auxiliary space where h is the tree height, representing the recursion stack depth.

← All Problems