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.
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.
Constraints:
- The number of nodes in the tree is in the range [1, 104].
- 0 <= Node.val <= 104
Solve it on LeetCode
Approaches
1. Recursive DFS (Depth-First Search)
Intuition:
The problem is an extension of the House Robber problem. Here, the houses are in the form of a binary tree, and the rule is the same: we cannot rob two directly-linked houses. A straightforward way to solve this problem is to use DFS and recursion to consider all possible combinations of robbing/not robbing a node and calculate the maximum amount.
The basic idea is:
- For each node, we have two choices: rob this house or not.
- If we rob this house, we cannot rob its children but can consider its grandchildren.
- If we do not rob this house, we can move to its children freely.
Code:
- Time Complexity: O(2^n) - For each node, two recursive calls are made, leading to an exponential number of calls.
- Space Complexity: O(n) - In the worst case, the depth of the recursion tree can go up to N, the number of nodes in the tree.
2. DFS with Memoization
Intuition:
To optimize the above approach, we implement memoization. The recursive approach recalculates the same values multiple times. Instead, we can store the results for each subtree for a node, which saves computation time.
We use a HashMap to store the result for each node so we don't compute the value of a node more than once.
Code:
- Time Complexity: O(n) - Each node is visited once, and results are stored and reused.
- Space Complexity: O(n) - The extra space needed for the memo map as well as the recursion stack.
3. Optimized DFS with Return Values (Most Optimal)
Intuition:
Rather than relying solely on memoization, we can optimize further by using a pair of values returned for each node:
- The maximum money that can be robbed if the current node is not robbed.
- The maximum money that can be robbed if the current node is robbed.
This approach allows us to eliminate the use of an external hashmap by encompassing all information in a succinct recursive return.
Code:
- Time Complexity: O(n) - Each node is visited once, and each node provides instantaneous information for further computations.
- Space Complexity: O(h) - The depth of the recursion stack, where
his the height of the tree, due to recursion.