All problems

Binary Tree Maximum Path Sum

Hard · tree dfs

You are given the root of a binary tree. A path is a chain of nodes where each neighbouring pair is joined by an edge, and no node appears twice. A path may start and end at any node. It does not have to pass through the root, and it does not have to end at a leaf. It must contain at least one node.

The sum of a path is the total of the values of its nodes. Return the maximum sum over all possible paths. Values can be negative, so the best path may be a single node. If every value is negative, the answer is the largest single value.

Examples

Example 1

Input: root = [1, 2, 3]

Output: 6

The path 2 -> 1 -> 3 goes up through the root and adds to 2 + 1 + 3 = 6.

Example 2

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

Output: 42

The best path is 15 -> 20 -> 7 and it skips the root: 15 + 20 + 7 = 42. Including -10 would only lower it.

Example 3

Input: root = [-3]

Output: -3

A path needs at least one node, so the answer is -3, not 0.

Constraints