Last updated on January 13th, 2025 at 03:17 am
Here, we see a House Robber III LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Depth-First Search, Tree
Companies
Uber
Level of Question
Medium
House Robber III LeetCode Solution
Table of Contents
1. Problem Statement
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:
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is “Tree Depth First Search (DFS)”. This is evident because the solution involves recursively traversing the tree in a depth-first manner to calculate the maximum amount of money that can be robbed without alerting the police. The DFS approach is used to explore all possible combinations of robbing or skipping nodes in the tree.
The C++ code, however, uses a “Tree Breadth-First Search (BFS)” approach to first group the nodes by levels and then applies a dynamic programming approach to calculate the maximum amount that can be robbed. This makes the C++ implementation slightly different from the others.
3. Code Implementation in Different Languages
3.1 House Robber III C++
class Solution {
public:
int rob(TreeNode* root) {
if (!root) return 0;
vector<int> houseRows;
int len = 1, dp[3];
TreeNode *curr;
queue<TreeNode*> q;
q.push(root);
while (len) {
houseRows.push_back(0);
while (len--) {
curr = q.front();
q.pop();
houseRows.back() += curr->val;
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
len = q.size();
}
len = houseRows.size();
dp[0] = houseRows[0];
dp[1] = max(houseRows[0], houseRows[1]);
dp[2] = max(houseRows[2] + dp[0], dp[1]);
for (int n: dp) cout << n << ' ';
for (int i = 3; i < len; i++) {
dp[i % 3] = max(dp[(i - 1) % 3], max(dp[(i - 3) % 3], dp[(i - 2) % 3]) + houseRows[i]);
}
return dp[--len % 3];
}
};
3.2 House Robber III Java
public class Solution {
public int rob(TreeNode root) {
int[] num = dfs(root);
return Math.max(num[0], num[1]);
}
private int[] dfs(TreeNode x) {
if (x == null) return new int[2];
int[] left = dfs(x.left);
int[] right = dfs(x.right);
int[] res = new int[2];
res[0] = left[1] + right[1] + x.val;
res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return res;
}
}
3.3 House Robber III JavaScript
var rob = function(root) {
function helper(node){
if(!node) return [0,0];
const [lr,ln] = helper(node.left);
const [rr, rn] = helper(node.right);
return [node.val + ln + rn, Math.max(lr+rr, ln+rn, lr+rn, ln+rr)];
}
return Math.max(...helper(root));
};
3.4 House Robber III Python
class Solution(object):
def rob(self, root):
return max(self.dfs(root))
def dfs(self, root):
if not root:
return (0, 0)
left = self.dfs(root.left)
right = self.dfs(root.right)
return (root.val + left[1] + right[1], max(left[0], left[1]) + max(right[0], right[1]))
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(N) | O(N) |
| Java | O(N) | O(H) |
| JavaScript | O(N) | O(H) |
| Python | O(N) | O(H) |
where, H is the height of the tree.
- The C++ implementation uses Tree BFS + Dynamic Programming.
- The Java, JavaScript, and Python implementations use Tree DFS.
- All implementations have a time complexity of O(N), but the space complexity varies slightly due to the use of BFS in C++.