Binary Tree Maximum Path Sum

Given a binary tree, return the maximum path sum among all non-empty paths. A path may start and end at any nodes, but it must go downward along parent-child connections without revisiting nodes. Tree DP is needed because every node contributes to a best path that passes through it or extends upward.

Input Format

tree = level-order binary tree with null markers

Output Format

maximum path sum

Constraints

  • 1 <= number of nodes <= 10^5
  • Node values may be negative.
  • The tree is given in level-order form with null markers.

Examples

Example 1:

Input:

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

Output:

42

Explanation:

The best path is 15 -> 20 -> 7 with sum 42.

Example 2:

Input:

tree = [1,2,3]

Output:

6

Explanation:

The path 2 -> 1 -> 3 gives the maximum sum.

Loading...
Binary Tree Maximum Path Sum - Advanced Trees