FunctionRacerProblemsRace

Longest Counting Path

HardTreesPython, JavaScript, TypeScript, Java, C++

You are given the root of a binary tree. A path joins nodes by parent and child links and uses no node twice. It may climb from a node up to an ancestor and then go down the other side.

A path counts when its values, read from one end to the other, go up by exactly 1 at every step, like 4, 5, 6.

Return the number of nodes on the longest counting path. A single node is a counting path of length 1.

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 [3,2,4,1,null,null,5]
returns 5

The path 1, 2, 3, 4, 5 starts at the leaf 1, climbs to the root 3 and goes down the other side.

Example 2

root [1,2,3]
returns 2

Only 1 and 2 are one apart. The path 2, 1, 3 does not count from either end.

Example 3

root [3,4,4]
returns 2

Both children are 4, so the root can join only one of them: 3, 4.

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