#337

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

House Robber III

Maximize the loot by robbing non-adjacent houses in a binary tree structure using dynamic programming and DFS.

dynamic programming tree depth first search binary tree

Problem Statement

The thief has infiltrated a new area where the houses form a binary tree. The only way to move between houses is through their parent-child relationships. If two directly-linked houses are robbed on the same night, the police will be alerted. The goal is to determine the maximum money the thief can rob, ensuring no adjacent houses are targeted.

Given the root of the binary tree, your task is to calculate the maximum amount of money that can be robbed while following these rules. The number of houses (nodes) can go up to 10^4, and each house has a non-negative value representing the amount of money inside.

Examples

Example 1

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

Output: 7

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

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

Constraints

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

Solution Approach

Dynamic Programming with DFS

We can utilize dynamic programming and depth-first search (DFS) to traverse the tree while tracking two states: the maximum loot when a house is robbed and when it is skipped. At each node, we'll compute the maximum loot by considering both cases and ensuring no two adjacent houses are robbed.

State Tracking

For each node, we maintain two values: one for the maximum loot when the current house is robbed and another when it is skipped. By combining these values for each node in a post-order DFS traversal, we can compute the global maximum loot while maintaining the non-adjacency constraint.

Memoization to Optimize

To optimize the solution, we can use memoization to store the results of subproblems (robbed and skipped states for each node). This avoids recomputing results for already visited nodes, improving performance significantly, especially for large trees.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n), where n is the number of nodes in the tree, as we visit each node once. The space complexity is O(h), where h is the height of the tree due to the recursion stack during the DFS traversal, or O(n) if memoization is used to store subproblem results.

What Interviewers Usually Probe

Look for the candidate's ability to traverse a binary tree efficiently using DFS.
Assess their understanding of dynamic programming and state tracking in tree problems.
Evaluate if they can handle large inputs effectively by applying memoization techniques.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for the constraint that no two directly-linked houses can be robbed.
Overlooking the importance of memoization in improving time complexity for larger trees.
Failing to properly track and compare both robbed and skipped states for each node.

Follow-up variants

Modify the problem to work with a general graph instead of a binary tree, adding complexity in terms of adjacency.
Introduce a limit on the number of houses that can be robbed in a single night, adding an extra layer of optimization.
Change the tree to a non-binary tree, where each node can have an arbitrary number of children, altering the DFS approach.

FAQ

How do I maximize the loot in the House Robber III problem?

By using dynamic programming with DFS to track the maximum loot while ensuring no two directly connected houses are robbed on the same night.

What is the time complexity of the solution?

The time complexity is O(n), where n is the number of nodes in the tree, due to the DFS traversal.

Can I use memoization in this problem?

Yes, memoization helps avoid redundant calculations and significantly improves performance in larger trees.

What happens if I rob adjacent houses?

Robbing adjacent houses will trigger an alert to the police, violating the problem's constraints.

What is the primary pattern used to solve House Robber III?

The primary pattern is binary-tree traversal combined with state tracking through dynamic programming.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# 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 dfs(root: Optional[TreeNode]) -> (int, int):
            if root is None:
                return 0, 0
            la, lb = dfs(root.left)
            ra, rb = dfs(root.right)
            return root.val + lb + rb, max(la, lb) + max(ra, rb)

        return max(dfs(root))

Continue Practicing

#124 binary tree maximum path sum #968 binary tree cameras #1372 longest zigzag path in a binary tree