Binary Tree Maximum Path Sum
Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Tags: Tree
Try It!
Discussion
Video
Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.res = float('-inf')
self.helper(root)
return self.res
def helper(self, root):
if not root:
return 0
left = self.helper(root.left)
right = self.helper(root.right)
if root.val + left + right > self.res:
self.res = root.val + left + right
pos_max_path = root.val + max(left, right)
if pos_max_path > 0:
return pos_max_path
else:
return 0