Hard · Trees

Binary Tree Maximum Path Sum

Given the root of a non-empty binary tree, return the maximum path sum, where a path is a sequence of nodes joined by parent–child edges that uses each node at most once, contains at least one node, and need not pass through the root.

Examples

Example 1

[-10,9,20,null,null,15,7] → 42

Output: max path = 42

Example 2

[1,2,3] → 6

Output: max path = 6

Rebuild it in the studio

Open every published interview problem, solution, scene, and memory room free, with no account.