Binary Tree Maximum Path Sum
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node's values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
class Solution:
def __init__(self):
self.maxSum = float('-inf')
def maxPathSum(self, root: TreeNode) -> int:
def traverse(root):
if root:
left = traverse(root.left)
right = traverse(root.right)
self.maxSum = max(self.maxSum,root.val, root.val + left, root.val + right, root.val + left + right)
return max(root.val,root.val + left,root.val + right)
else:
return 0
traverse(root)
return self.maxSumPosted by Jamie Meyer 18 days ago