Python 0337.py
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
@cache
def deeper(node, rob):
if not node:
return 0
if rob:
return deeper(node.left, False) + deeper(node.right, False) + node.val
l = max(deeper(node.left, True), deeper(node.left, False))
r = max(deeper(node.right, True), deeper(node.right, False))
return l + r
return max(deeper(root, True), deeper(root, False))
Difficulty
and has an acceptance rate of about 56% (900k+ submissions).
Typical patterns to solve this problem:
- Binary Tree
- Depth First Search
- Dynamic Programming
- Tree
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation solves the classic “House Robber III” problem on a binary tree. The goal is to compute the maximum amount of money that can be collected without robbing two directly-connected nodes. The solution uses a depth-first recursion with memoization to explore both possibilities-robbing the current node or skipping it-while caching intermediate results to avoid repeated work.
Core Logic
The algorithm is centered around the nested function deeper. This helper receives a tree node and a Boolean flag rob that indicates whether the caller intends to rob the current node. The function returns the optimal amount that can be obtained from the subtree rooted at node under the given constraint.
@cache
def deeper(node, rob):
if not node:
return 0
...
The @cache decorator (from functools) automatically stores the result of each (node, rob) pair. Subsequent calls with the same arguments retrieve the cached value instantly, eliminating exponential recomputation.
When the Current Node Must Be Robbed
If rob is True, the algorithm is forced to include node.val in the total. Because two adjacent houses cannot both be robbed, the children must be visited with rob=False. The return expression adds the value of the current node to the optimal amounts from both subtrees when they are not robbed.
if rob:
return deeper(node.left, False) + deeper(node.right, False) + node.val
When the Current Node May Be Skipped
When rob is False, the algorithm is free to decide for each child whether to rob it or not. It computes the best outcome for the left child by taking the maximum of robbing and not robbing that child, and does the same for the right child. The sum of these two maxima yields the optimal amount for the current subtree when the current node is not taken.
l = max(deeper(node.left, True), deeper(node.left, False))
r = max(deeper(node.right, True), deeper(node.right, False))
return l + r
Entry Point
The public method rob initiates the recursion by evaluating both possibilities for the root node-robbing it or not-and returns the larger of the two results.
return max(deeper(root, True), deeper(root, False))
Edge Cases Handled
The base case if not node: return 0 gracefully handles an empty tree, a missing child, or a completely null input. Because the function returns zero for a non-existent node, the recursion naturally collapses without special-case logic for leaf nodes. The same base case also covers trees consisting of a single node; the algorithm correctly returns either the node’s value (when robbed) or zero (when not robbed), and the outer max selects the appropriate amount.
When the tree is highly unbalanced-e.g., a chain of left children only-the memoization still prevents redundant calculations because each (node, rob) pair is cached exactly once, regardless of depth.
Performance Optimizations
The most significant optimization is the use of @cache. Without caching, the naïve recursion would explore an exponential number of state combinations, repeatedly evaluating identical subproblems. By storing the result of each (node, rob) pair, the algorithm reduces the effective work to a linear number of distinct states, proportional to the number of nodes times two (one for each Boolean flag).
Another subtle optimization is the early return for None nodes, which avoids unnecessary function calls deeper in the call stack. The decision to compute max only once per child (instead of recomputing the same sub-calls multiple times) further leverages the cache, ensuring that each child’s optimal values are retrieved from memory rather than recomputed.
The recursion follows a post-order traversal pattern: it first resolves the results for the left and right subtrees before combining them at the current node. This ordering aligns naturally with the cache’s ability to provide already-computed results for child subtrees, minimizing the call depth and keeping the call stack bounded by the height of the tree.
ELI5 - Simplified Explanation
Imagine a row of houses shaped like a tree connected by branches. Each house has a pile of shiny gold coins inside. There is a sneaky rule for this game: if a house is chosen to be emptied, the houses directly touching it on either side must stay closed and quiet.
The code starts at the very top of the tree structure. It looks at a house and asks two questions. First, does it want to take the gold from this house? If the answer is yes, it adds those coins to its total but then must skip the houses immediately below it. Second, does it want to skip this house instead? if it skips, it is free to look at the houses below and pick the best pile from either the left or the right side.
To keep things fast, the code uses a special trick to remember the answer for every house it has already visited. This way, it never has to do the same work twice. It moves down the branches step by step, exploring every possible path, and keeps track of which choices lead to the biggest mountain of treasure. By the time it reaches the bottom of the tree, it has carefully weighed every option to find the secret path that lets it walk away with the most gold possible.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||
| WalkCCC | C++ | Python | Java | |||||||
| leetcode.ca | C++ | Python | Java | Go | TS | |||||
| LeetcodeHelp | C++ | Python | Java | |||||||
| MemoryLimitExceeded | C++ | Python | ||||||||
| Progiez | C++ | Python | Java | |||||||
| github | begeekmyfriend | C | ||||||||
| black-shadows | C++ | |||||||||
| charles-wangkai | Java | |||||||||
| chenyanzhe | C++ | |||||||||
| everthis | JS | |||||||||
| FelixFan1122 | C# | |||||||||
| fpdjsns | C++ | |||||||||
| fsq | C++ | |||||||||
| halfrost | Go | |||||||||
| haoel | C++ | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| MacJim | C++ | |||||||||
| qiyuangong | Python | |||||||||
| ruoru | Rust | |||||||||
| sonugiri1043 | C++ | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| vli02 | C | |||||||||
| vthwang | Java | |||||||||
| wisdompeak | C++ | |||||||||
| XiaotaoGuo | C++ | |||||||||
| zfang399 | C++ | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | |||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||
| MemoryLimitExceeded | Python, C++ | |||||||||
| Progiez | C++, Java, Python | |||||||||
| begeekmyfriend | C | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| chenyanzhe | C++ | |||||||||
| everthis | JavaScript | |||||||||
| FelixFan1122 | C# | |||||||||
| fpdjsns | C++ | |||||||||
| fsq | C++ | |||||||||
| halfrost | Go | |||||||||
| haoel | C++ | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| linouk23 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| MacJim | C++ | |||||||||
| qiyuangong | Python | |||||||||
| ruoru | Rust | |||||||||
| sonugiri1043 | C++ | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| varunu28 | Java | |||||||||
| vli02 | C | |||||||||
| vthwang | Java | |||||||||
| wisdompeak | C++ | |||||||||
| XiaotaoGuo | C++ | |||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 198: House Robber
- problem 213: House Robber II
Solved On The Same Day
- problem 101: Symmetric Tree
- problem 790: Domino and Tromino Tiling
- problem 1035: Uncrossed Lines
- problem 115: Distinct Subsequences
- problem 124: Binary Tree Maximum Path Sum
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality