Maximum Path Sum in Binary Tree

Problem Statement

Given a non-empty binary tree, determine the highest sum of values along any path.

Here, a path is any sequence of nodes connected through parent-child links, starting and ending at any nodes in the tree. The path must include at least one node, but it does not have to pass through the tree's root.

Examples

Example 1:
Tree nodes: [3,4,5]

      3
     / \
    4   5

Maximum path sum: 12

Example 2:
Tree nodes: [-15,10,25,null,null,20,30]

       -15
       /  \
     10    25
           /  \
         20    30

Maximum path sum: 75

Constraints

• Number of nodes in the tree is between 1 and 3000.
• Each node's value ranges from -1000 to 1000.