Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Binary Tree Maximum Path Sum
Bookmark
Input
Example 1
Example 2
All Negative
Custom
tree
=
[-10, 9, 20, null, null, 15, 7]
-10
9
20
15
7
maxSum
?
a path bends at one node and uses at most two arms
-10
9
20
15
7
maxSum
?
a path bends at one node and uses at most two arms
-10
9
20
15
7
maxSum
?
gain(
9
)
-10
9
20
15
7
maxSum
9
maxSum =
9
-10
9
20
15
7
g=+9
maxSum
9
gain(
20
)
-10
9
20
15
7
g=+9
maxSum
9
right is null:
0
-10
9
20
15
7
g=+9
g=+15
maxSum
15
right arm gain (clamp negatives to
0
)
-10
9
20
15
7
g=+9
g=+15
maxSum
15
path at
7
:
7
+
0
+
0
=
7
-10
9
20
15
7
g=+9
g=+15
g=+7
maxSum
15
path at
20
:
20
+
0
+
7
=
42
-10
9
20
15
7
g=+9
g=+35
g=+15
g=+7
maxSum
42
path at
-10
:
-10
+
0
+
35
=
34
-10
9
20
15
7
g=+25
g=+9
g=+35
g=+15
g=+7
maxSum
42
max = 42
algo
master
.
io
Step:
Start: the max path can bend at any node and use any two of its arms
0 / 37
Input
Example 1
Example 2
All Negative
Custom
tree
=
[-10, 9, 20, null, null, 15, 7]
0 / 37
algo
master
.
io
Step:
Start: the max path can bend at any node and use any two of its arms
