#124
Binary Tree Maximum Path Sum
hard· Treesruns: 0A path in a binary tree is a sequence of nodes where each adjacent pair has an edge connecting them. A node can appear in the sequence at most once. The path does not need to pass through the root. Given the root of a binary tree, return the maximum path sum of any non-empty path.
sign in to paste and practice your own solution
wpm 0acc 100%time 0:000 / 455
class Solution:
def maxPathSum(self, root: TreeNode | None) -> int:
best = float("-inf")
def gain(node: TreeNode | None) -> int:
nonlocal best
if not node:
return 0
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
best = max(best, node.val + left + right)
return node.val + max(left, right)
gain(root)
return best
click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause
desktop only
codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.
you can still browse problems and sections from your phone.