#0324Time: O(2^N), where N is the number of nodes. The recursive calls branch out exponentially as many subproblems are recomputed.Space: O(H), where H is the height of the tree. In the worst case of a skewed tree, this becomes O(N). This space is used by the recursion stack.2 companies
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
Approaches
3 approaches with complexity analysis and trade-offs.
A straightforward recursive approach that directly translates the problem's logic. For each node, it calculates the maximum profit by considering two scenarios: robbing the current house or skipping it.
Algorithm
Define a function rob(node).
Base Case: If node is null, return 0.
Calculate the profit if we rob the current node (robCurrent):
Initialize robCurrent = node.val.
If node.left is not null, add rob(node.left.left) + rob(node.left.right).
If node.right is not null, add rob(node.right.left) + rob(node.right.right).
Calculate the profit if we skip the current node (skipCurrent):
skipCurrent = rob(node.left) + rob(node.right).
Return max(robCurrent, skipCurrent).
Walkthrough
The core idea is to define a recursive function, say rob(node), which computes the maximum money that can be robbed from the subtree rooted at node.
At each node, we have two choices:
Rob the current node: If we rob node, we gain node.val but cannot rob its immediate children (node.left and node.right). We can, however, rob its grandchildren. The total amount would be
Do not rob the current node: If we skip node, we are free to rob its children. The total amount would be rob(node.left) + rob(node.right).
The function rob(node) returns the maximum of these two options.
The base case for the recursion is when a node is null, in which case it returns 0.
This approach suffers from severe performance issues due to re-calculating the same subproblems multiple times. For instance, rob(grandchild) is computed independently by both rob(parent) and rob(grandparent).
1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 * int val;5 * TreeNode left;6 * TreeNode right;7 * TreeNode() {}8 * TreeNode(int val) { this.val = val; }9 * TreeNode(int val, TreeNode left, TreeNode right) {10 * this.val = val;11 * this.left = left;12 * this.right = right;13 * }14 * }15 */16class Solution {17 public int rob(TreeNode root) {18 if (root == null) {19 return 0;20 }2122 // Option 1: Rob the root node23 int robRoot = root.val;24 if (root.left != null) {25 robRoot += rob(root.left.left) + rob(root.left.right);26 }27 if (root.right != null) {28 robRoot += rob(root.right.left) + rob(root.right.right);29 }3031 // Option 2: Don't rob the root node32 int skipRoot = rob(root.left) + rob(root.right);3334 return Math.max(robRoot, skipRoot);35 }36}
Complexity
Time
O(2^N), where N is the number of nodes. The recursive calls branch out exponentially as many subproblems are recomputed.
Space
O(H), where H is the height of the tree. In the worst case of a skewed tree, this becomes O(N). This space is used by the recursion stack.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem's constraints.
Cons
Extremely inefficient due to massive redundant computations.
Will likely result in a 'Time Limit Exceeded' error for larger trees.
This approach improves upon the brute-force recursion by using a hash map to store the results of subproblems that have already been solved. This technique is known as memoization, a form of dynamic programming.
Algorithm
Create a Map<TreeNode, Integer> memo to store computed results.
Define a helper function rob(node, memo).
Base Case: If node is null, return 0.
Memoization Check: If memo contains node, return memo.get(node).
Calculate robCurrent and skipCurrent as in the brute-force approach, making recursive calls with the memo map.
result = max(robCurrent, skipCurrent).
Store the result: memo.put(node, result).
Return result.
Walkthrough
The overlapping subproblems issue in the brute-force approach can be solved by caching the results. We use a hash map memo where the key is a TreeNode and the value is the maximum amount of money that can be robbed from the subtree rooted at that node.
The recursive function, rob(node, memo), first checks if the result for the current node is already in the memo map.
If it is, the cached value is returned immediately, avoiding re-computation.
If not, it calculates the result just like in the brute-force approach: by comparing the profit from robbing the current node versus skipping it.
Before returning, the computed result is stored in the memo map for future use.
This ensures that the subproblem for each node is solved only once.
1import java.util.Map;2import java.util.HashMap;34class Solution {5 public int rob(TreeNode root) {6 return rob(root, new HashMap<>());7 }89 private int rob(TreeNode node, Map<TreeNode, Integer> memo) {10 if (node == null) {11 return 0;12 }13 if (memo.containsKey(node)) {14 return memo.get(node);15 }1617 // Option 1: Rob the current node18 int robCurrent = node.val;19 if (node.left != null) {20 robCurrent += rob(node.left.left, memo) + rob(node.left.right, memo);21 }22 if (node.right != null) {23 robCurrent += rob(node.right.left, memo) + rob(node.right.right, memo);24 }2526 // Option 2: Skip the current node27 int skipCurrent = rob(node.left, memo) + rob(node.right, memo);2829 int result = Math.max(robCurrent, skipCurrent);30 memo.put(node, result);31 return result;32 }33}
Complexity
Time
O(N), where N is the number of nodes. Each subproblem (for each node) is computed only once thanks to memoization.
Space
O(N), where N is the number of nodes. The `memo` map can store up to N entries, and the recursion stack can go up to O(H) (O(N) in the worst case).
Trade-offs
Pros
Significantly more efficient than brute-force.
Guarantees each subproblem is solved only once, leading to a polynomial time complexity.
Cons
Uses O(N) extra space for the memoization map, which can be significant for large trees.
This is the most efficient approach. Instead of a recursive function that returns a single value, we design a function that returns a pair of values for each node: the maximum profit if the node is robbed, and the maximum profit if the node is not robbed. This avoids the need to make recursive calls to grandchildren.
Algorithm
Define a helper function robSub(node) that returns an array of two integers [robbed, skipped].
Base Case: If node is null, return [0, 0].
Recursively call on children:
left = robSub(node.left)
right = robSub(node.right)
Calculate profit for the current node:
robbed = node.val + left[1] + right[1] (rob current, so must skip children).
skipped = max(left[0], left[1]) + max(right[0], right[1]) (skip current, so take max from children).
Return [robbed, skipped].
The main function calls robSub(root) and returns max(result[0], result[1]).
Walkthrough
We can observe that to decide the maximum profit for a node, we only need information from its immediate children, not its grandchildren.
Let's define a helper function, robSub(node), that performs a post-order traversal and returns an array of two integers for each node: [max_if_robbed, max_if_skipped].
max_if_robbed: The maximum profit from the subtree at node, assuming we rob node.
max_if_skipped: The maximum profit from the subtree at node, assuming we skip node.
The logic is as follows:
Recursively call robSub on the left and right children to get their respective profit pairs: leftPair and rightPair.
To calculate max_if_robbed for the current node: We must rob node, so we cannot rob its children. The profit is node.val + leftPair[1] + rightPair[1] (where leftPair[1] and rightPair[1] are the profits from skipping the children).
To calculate max_if_skipped for the current node: We skip node, so we are free to either rob or skip its children. We take the maximum possible from each child's subtree. The profit is max(leftPair[0], leftPair[1]) + max(rightPair[0], rightPair[1]).
The base case is a null node, for which we return [0, 0].
The final answer for the root of the tree is the maximum of the two values returned by robSub(root).
1class Solution {2 public int rob(TreeNode root) {3 int[] result = robSub(root);4 return Math.max(result[0], result[1]);5 }67 // Returns an array of size 2: [max_if_robbed, max_if_skipped]8 private int[] robSub(TreeNode node) {9 if (node == null) {10 return new int[]{0, 0};11 }1213 int[] left = robSub(node.left);14 int[] right = robSub(node.right);1516 // If we rob the current node, we cannot rob its children.17 // Profit = current_node_value + profit_from_skipping_left_child + profit_from_skipping_right_child18 int robbed = node.val + left[1] + right[1];1920 // If we skip the current node, we can either rob or skip its children.21 // We take the max profit from the left and right subtrees.22 // Profit = max(profit_from_robbing_left, profit_from_skipping_left) + max(profit_from_robbing_right, profit_from_skipping_right)23 int skipped = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);2425 return new int[]{robbed, skipped};26 }27}
Complexity
Time
O(N), where N is the number of nodes. We visit each node exactly once.
Space
O(H), where H is the height of the tree, for the recursion stack. This is O(log N) for a balanced tree and O(N) for a skewed tree. This is better than the O(N) space required for the memoization map in the previous approach.
Trade-offs
Pros
Most efficient in both time and space.
Clean logic based on post-order traversal.
Avoids the overhead of a hash map and complex recursive calls to grandchildren.
Cons
The state representation (returning a pair/array) might be slightly less intuitive at first glance compared to the direct recursive approach.
Solutions
Solution
1public class House_Robber_III { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution_singleRecursion { public int rob ( TreeNode root ) { return Math . max ( dfs ( root , true ), dfs ( root , false )); } private int dfs ( TreeNode root , boolean isCurrentRootRobbed ) { if ( root == null ) { return 0 ; } if ( isCurrentRootRobbed ) { return root . val + dfs ( root . left , false ) + dfs ( root . right , false ); } else { // child can be either rob or no-rob return Math . max ( dfs ( root . left , true ), dfs ( root . left , false )) + Math . max ( dfs ( root . right , true ), dfs ( root . right , false )); } } } class Solution { /* 1. node value can be negative? */ public int rob ( TreeNode root ) { if ( root == null ) { return 0 ; } return Math . max ( target ( root ), skip ( root )); } private int target ( TreeNode root ) { if ( root == null ) { return 0 ; } return root . val + skip ( root . left ) + skip ( root . right ); } private int skip ( TreeNode root ) { if ( root == null ) { return 0 ; } // @note: not target, but rob again => 因为理论上可以连续skip两层 // return target(root.left) + target(root.right); return rob ( root . left ) + rob ( root . right ); } } } ///////// /** * 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 { private Map < TreeNode , Integer > memo ; public int rob ( TreeNode root ) { memo = new HashMap <>(); return dfs ( root ); } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } if ( memo . containsKey ( root )) { return memo . get ( root ); } int a = dfs ( root . left ) + dfs ( root . right ); int b = root . val ; if ( root . left != null ) { b += dfs ( root . left . left ) + dfs ( root . left . right ); } if ( root . right != null ) { b += dfs ( root . right . left ) + dfs ( root . right . right ); } int res = Math . max ( a , b ); memo . put ( root , res ); return res ; } }
1class Solution : def rob ( self , root : TreeNode ) -> int : return max ( self . dfs ( root , True ), self . dfs ( root , False )) # if no cache, then running time over limit @ cache def dfs ( self , root : TreeNode , isCurrentRootRobbed : bool ) -> int : if not root : return 0 if isCurrentRootRobbed : return root . val + self . dfs ( root . left , False ) + self . dfs ( root . right , False ) else : return self . rob ( root . left ) + self . rob ( root . right ) # below else logic also passing OJ # return max(self.dfs(root.left, True), self.dfs(root.left, False)) + max(self.dfs(root.right, True), self.dfs(root.right, False)) ########### # better and concise class Solution : # post-order def rob ( self , root : TreeNode ) -> int : def dfs ( node ): if not node : return 0 , 0 left , right = dfs ( node . left ), dfs ( node . right ) rob = node . val + left [ 1 ] + right [ 1 ] # [1] meaming left/right children skippted skip = max ( left ) + max ( right ) return rob , skip return max ( dfs ( root )) ########### class Solution : # return in else is too lengthy... def rob ( self , root : TreeNode ) -> int : return max ( self . dfs ( root , True ), self . dfs ( root , False )) # if no cache, then running time over limit @ cache def dfs ( self , root : TreeNode , isCurrentRootRobbed : bool ) -> int : if not root : return 0 if isCurrentRootRobbed : return root . val + self . dfs ( root . left , False ) + self . dfs ( root . right , False ) else : return max ( self . dfs ( root . left , True ), self . dfs ( root . left , False )) + max ( self . dfs ( root . right , True ), self . dfs ( root . right , False ))
1// OJ: https://leetcode.com/problems/house-robber-iii/ // Time: O(N) // Space: O(H) class Solution { pair < int , int > dfs ( TreeNode * root ) { // rob, skip if ( ! root ) return { 0 , 0 }; auto [ lr , ls ] = dfs ( root -> left ); auto [ rr , rs ] = dfs ( root -> right ); return { root -> val + ls + rs , max ( lr , ls ) + max ( rr , rs ) }; } public: int rob ( TreeNode * root ) { auto [ r , s ] = dfs ( root ); return max ( r , s ); } };
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
