FunctionRacerProblemsRace

Best Path Anywhere

HardTreesPython, JavaScript, TypeScript, Java, C++

You are given the root of a binary tree whose values may be negative.

A path is a chain of nodes in which every node is joined to the next one by a parent and child link, and no node is used twice. A path holds at least one node. It may start and end anywhere, and it does not have to pass through the root.

Return the largest sum of values that a path can have.

Trees appear in the tests in level order, with null for a missing child, like [3,9,20,null,null,15,7]. Each node is a TreeNode with .val, .left and .right; the class is already defined for you.

Example 1

root [5,-3,4,2,6]
returns 12

The path 6, -3, 5, 4 climbs from a leaf to the root and goes down the other side: 6 - 3 + 5 + 4 = 12.

Example 2

root [-7]
returns -7

The only path is the single node.

Example 3

root [-2,9,-1]
returns 9

The node 9 alone beats any longer path, because the root would take 2 away.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Trees problems