📘

Binary Tree Maximum Path Sum

Given a binary tree as a level-order array, find the maximum path sum. A path can start and end at any node and goes along parent-child connections. Each node can only appear once in the path.

Example:

Input:

-10,9,20,null,null,15,7

Output:

Reasoning:

The binary tree is constructed from the level-order array: the root node is -10, its children are 9 and 20, and 20's children are 15 and 7.
We calculate the path sum for each possible path in the tree, considering that each node can only appear once in the path.
The maximum path sum is found in the path 20 -> 15 -> 7, but also considering the root's child 20, the path -10 -> 20 -> 15 -> 7 has a lower sum, however, 20 -> 15 -> 7 has a sum of $20 + 15 + 7 = 42$ .
The final output is the maximum path sum found, which is 42.

Constraints:

1 <= number of nodes <= 3 * 10^4
-1000 <= Node.val <= 1000

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.