/298. Longest Consecutive Sequence in Binary Tree

298. Longest Consecutive Sequence in Binary Tree

Medium

Trees54.7% acceptance

Given the root node of a binary tree, determine the length of the longest path consisting of consecutive integers (increasing by 1) from parent to child. The path must be downward (from parent to child), and can start at any node. Return the length of the longest such path.

Example 1

Input: TreeNode(7, TreeNode(8, TreeNode(9)), TreeNode(6))

Output: 3

Explanation: The path 7 -> 8 -> 9 is consecutive and has length 3.

Example 2

Input: TreeNode(10, TreeNode(11, None, TreeNode(12)), TreeNode(9))

Output: 3

Explanation: The path 10 -> 11 -> 12 is consecutive and has length 3.

Example 3

Input: TreeNode(5, TreeNode(4), TreeNode(6, TreeNode(7)))

Output: 2

Explanation: The path 6 -> 7 is consecutive and has length 2.

Constraints

1 <= number of nodes in the tree <= 2500
-2^31 <= node value <= 2^31 - 1

Python (current runtime)

Case 1

Input: TreeNode(1, TreeNode(2, TreeNode(3)), TreeNode(4))

Expected: 3

Case 2

Input: TreeNode(15, TreeNode(16, TreeNode(17)), TreeNode(14, TreeNode(15)))

Expected: 3

Case 3

Input: TreeNode(20, TreeNode(21), TreeNode(22, TreeNode(23)))

Expected: 2

Case 4

Input: TreeNode(100)

Expected: 1