#124

Binary Tree Maximum Path Sum

master · 1640 · lc hard +32 · verified · 42.1% accepted · 18,352 likes · top 23%

⚑ Tree DP ⚑ Tree Path Sum / Maximum Path

Description

A path in a binary tree is any sequence of nodes where adjacent nodes share an edge, and each node appears at most once. The path does not need to pass through the root.

The path sum is the total of all node values in the path.

Given the root of a binary tree, return the maximum path sum across all non-empty paths.

Example 1:

Input: root = [1,2,3]

Output: 6

Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]

Output: 42

Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Code

# 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: Optional[TreeNode]) -> int:

# 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: Optional[TreeNode]) -> int: