Python 0124.py
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
@cache
def deeper(node, limit): # limit = max. direct child nodes
if not node:
return 0
if not node.left and not node.right:
self.best = max(self.best, node.val)
return node.val
l1 = deeper(node.left, 1)
r1 = deeper(node.right, 1)
l2 = deeper(node.left, 2)
r2 = deeper(node.right, 2)
me = node.val
if limit == 1:
result = max(me, me + l1, me + r1)
else: # limit == 2
result = max(me, me + l1, me + r1, me + l1 + r1)
self.best = max(self.best, result)
return result
self.best = root.val
deeper(root, 2)
return self.best
Difficulty
and has an acceptance rate of about 43% (4+ million 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 defines a class Solution with a method maxPathSum that computes the maximum sum obtainable by any path in a binary tree. A path is defined as a sequence of nodes where each consecutive pair is connected by a parent-child edge, and the path may start and end at any nodes in the tree. The algorithm uses a depth-first traversal combined with memoization to explore possible contributions from each subtree while maintaining a global best value.
Key Steps
The entry point maxPathSum initializes a mutable attribute self.best with the value of the root node and then invokes the nested helper function deeper on the root with a limit of 2.
self.best = root.val
deeper(root, 2)
return self.best
The helper deeper is decorated with @cache, which automatically stores the result of each call keyed by the node reference and the limit argument. This memoization prevents repeated evaluation of identical subproblems during the recursive exploration.
@cache
def deeper(node, limit):
...
Inside deeper, the first guard checks for a null node and returns 0. This base case ensures that leaf-level recursion terminates cleanly without contributing to the path sum.
if not node:
return 0
When a node is a leaf (both children are None), the algorithm updates the global best with the leaf’s value and returns that value as the maximum sum that can be extended upward from this leaf.
if not node.left and not node.right:
self.best = max(self.best, node.val)
return node.val
For internal nodes, the function recursively obtains four values: the best single-child contributions when the limit is 1 (l1 and r1) and the best contributions when the limit is 2 (l2 and r2). The limit parameter controls whether the current node may combine contributions from both children (limit == 2) or only a single child (limit == 1).
l1 = deeper(node.left, 1)
r1 = deeper(node.right, 1)
l2 = deeper(node.left, 2)
r2 = deeper(node.right, 2)
The variable me holds the node’s own value. The result for the current call is computed by considering different combinations based on the limit. When the limit is 1, the result is the maximum of the node alone, the node plus the left contribution, and the node plus the right contribution. When the limit is 2, the result also includes the possibility of adding both left and right contributions together with the node’s value.
me = node.val
if limit == 1:
result = max(me, me + l1, me + r1)
else: # limit == 2
result = max(me, me + l1, me + r1, me + l1 + r1)
After computing result, the global best is updated to reflect any larger path sum discovered at this node. The function then returns result, which represents the maximum sum that can be propagated upward to the node’s parent under the current limit constraint.
self.best = max(self.best, result)
return result
Edge Cases Handled
The algorithm explicitly handles the situation where the input tree consists of a single node. In that case, the leaf-node guard updates self.best with the node’s value and the recursion terminates, yielding the correct maximum path sum.
When a subtree is missing (i.e., a child reference is None), the early return of 0 ensures that absent branches do not contribute to the path sum, effectively treating them as neutral elements in the max calculations.
The limit parameter distinguishes between paths that may extend through both children versus those that must continue through only one child. This distinction allows the function to correctly evaluate paths that terminate at the current node versus those that pass through it, covering scenarios where the optimal path either bends at the node or proceeds linearly upward.
Performance Optimizations
Memoization via the @cache decorator is the primary optimization. By caching the results of deeper for each (node, limit) pair, the algorithm avoids recomputing the same subtree contributions multiple times, which is especially beneficial in trees with overlapping substructures or when the same node is visited under different limit contexts.
The use of a single mutable attribute self.best eliminates the need to propagate intermediate best values up the call stack, reducing the amount of data passed between recursive frames. Updating self.best immediately after each node’s computation ensures that the global optimum is always available without additional traversal.
Limiting the recursive calls to only the necessary combinations (limit == 1 and limit == 2) prevents unnecessary exploration of paths that would violate the problem’s constraints, thereby focusing computational effort on relevant scenarios.
Overall, the combination of memoization, in-place global tracking, and constrained recursion yields an efficient solution that scales well with the size of the input tree.
ELI5 - Simplified Explanation
Imagine a beautiful tree made of treasure chests instead of branches. Each chest has a number written on the lid, which represents how many gold coins are hiding inside it. The goal is to find the longest path through the tree that grabs the most gold possible.
The code starts at the very top of the tree, which is called the root. It sends out tiny explorers to peek into every single path. These explorers move down to the left and to the right, looking at the chests they find along the way.
There are two ways the explorers handle their collection. Sometimes, they are only allowed to follow one path down from a chest, and other times they are allowed to look at both the left and right sides together to make a bigger path. Every time an explorer finishes looking at a path, they check the total number of gold coins they found. They keep track of the highest number they have seen so far in a special box called best.
The explorers keep diving deeper and deeper into the tree until they reach the chests at the very tips of the branches. By the time they have visited every path, the special box will hold the biggest score discovered during the adventure.
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 | C# | Java | Rust | JS | Go | TS | |||
| LeetcodeHelp | C++ | Python | Java | ||||||||
| MemoryLimitExceeded | C++ | Python | |||||||||
| Progiez | C++ | Python | Java | ||||||||
| github | aylei | Rust | |||||||||
| begeekmyfriend | C | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| chenyanzhe | C++ | ||||||||||
| everthis | JS | ||||||||||
| FelixFan1122 | C# | ||||||||||
| fengvyi | C++ | ||||||||||
| fpdjsns | C++ | ||||||||||
| gaosq0604 | Python | ||||||||||
| Garvit244 | Python | ||||||||||
| gouthampradhan | Java | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| luangong | C++ | ||||||||||
| MacJim | C++ | ||||||||||
| qiyuangong | Python | ||||||||||
| ruoru | Rust | ||||||||||
| shreymehul | C# | ||||||||||
| sonugiri1043 | C++ | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| vli02 | C | ||||||||||
| wisdompeak | C++ | ||||||||||
| XiaotaoGuo | C++ | ||||||||||
| yuanliu666 | Kotlin | ||||||||||
| zfang399 | C++ | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript | ||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||
| MemoryLimitExceeded | Python, C++ | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| aylei | Rust | ||||||||||
| begeekmyfriend | C | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| chenyanzhe | C++ | ||||||||||
| everthis | JavaScript | ||||||||||
| FelixFan1122 | C# | ||||||||||
| fengvyi | C++ | ||||||||||
| fpdjsns | C++ | ||||||||||
| gaosq0604 | Python | ||||||||||
| Garvit244 | Python | ||||||||||
| gouthampradhan | Java | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| luangong | C++ | ||||||||||
| MacJim | C++ | ||||||||||
| qiyuangong | Python | ||||||||||
| ruoru | Rust | ||||||||||
| shreymehul | C# | ||||||||||
| sonugiri1043 | C++ | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| vli02 | C | ||||||||||
| wisdompeak | C++ | ||||||||||
| XiaotaoGuo | C++ | ||||||||||
| yuanliu666 | Kotlin | ||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 112: Path Sum
- problem 129: Sum Root to Leaf Numbers
- problem 666: Path Sum IV
- problem 687: Longest Univalue Path
- problem 1376: Time Needed to Inform All Employees
- problem 2322: Minimum Score After Removals on a Tree
- problem 2538: Difference Between Maximum and Minimum Price Sum
Solved On The Same Day
- problem 101: Symmetric Tree
- problem 337: House Robber III
- problem 790: Domino and Tromino Tiling
- problem 1035: Uncrossed Lines
- problem 115: Distinct Subsequences
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