Maximum Path Sum

Given the root of a binary tree, return the maximum path sum. A path may start and end at any node, but it must go down through parent-child links and contain at least one node. Pattern focus: Global Variable for Cross-Root Paths. Track the best path value seen anywhere in the tree.

Input Format

root = binary tree root

Output Format

maximum path sum in the tree

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= node values <= 10^4
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [1,2,3]

Output:

6

Explanation:

The best path is 2 -> 1 -> 3.

Example 2:

Input:

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

Output:

42

Explanation:

The best path is 15 -> 20 -> 7.

Loading...
Maximum Path Sum - Binary Tree DSA Problem