Leetcode - 337. House Robber III

Medium

Feb 19, 2026

#binary-tree

#dp

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 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.

Example 1:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

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

Constraints:

Notes

Intuition

We want to calculate the max amount the robber can take if they decide to steal from each house or to skip that house. Stealing would necessitate skipping over the direct children, and in the case of skipping we don't care whether we skip or take the child, we just want the max.

Implementation

In order to process nodes only once, we'll initialize a hashmap for the node stored with its take and skip value. Define the recursive DFS function, the base case checks if the node exists in the hashmap and early returns. Otherwise, we initialize a take value and skip value for the current node. The take value is initialized to the node's value and the skip value is initialized to zero. Then we iterate over each of the children and call the function recursively for each child. We add the skip value for the child to the take value for the current node to represent that the child is skipped when we decide to take the node. For the skip value of the current node we add the max of the take and skip value for the child because we don't care whether we skip the child or take it, we just want the max.

After iterating over the children, we save the node and the take and skip values in the hashmap to ensure processing only once and return them.

Finally, we call the function on the root node and take the max of the values.

Time: O(n), we iterate through each node once.
Space: O(n), the hashmap will contain all of the nodes as well as the call stack

Complexity

Solution

from typing import Optional, Tuple
from lcutils import TreeNode

# 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:
        if not root:
            return 0
        dp = {}
        def dfs(node: TreeNode) -> Tuple[int, int]:
            if node in dp:
                return dp[node]
            take_n = node.val
            skip_n = 0
            children = [node.left, node.right]
            for child in children:
                if not child:
                    continue
                take, skip = dfs(child)
                take_n += skip # if we decided to take the current node, direct children should be skipped
                skip_n += max(take, skip) # if we skip the current node, we don't care whether we take or skip the child, just want the max

            dp[node] = (take_n, skip_n)
            return dp[node]

        take, skip = dfs(root)
        return max(take, skip)



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()