Hard

Quiz

#124 Binary Tree Maximum Path Sum

APPROACH

A path in a binary tree is any sequence of nodes where adjacent nodes share an edge, and each node appears at most once. The path does not need to pass through the root.

The path sum is the total of all node values in the path.

Given the root of a binary tree, return the maximum path sum across all non-empty paths.

Example 1:

Input: root = [1,2,3]

Output: 6

Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

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

Output: 42

Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

1 of 4

1:00

What is the optimal approach for this problem?