NeetCode #400LC-298MediumTreesNC Algo100
← Back to All Problems#400 · #298 · Binary Tree Longest Consecutive Sequence(二叉树最长连续序列)
📌 Problem Statement & Constraints
Given the root of a binary tree, find the length of the longest consecutive path: a path where each node's value is exactly one greater than its parent's. The path must follow parent-child links and may go only downward. Constraints: the number of nodes is in
[1, 3 * 10^4].💡 Core Algorithmic Approaches
- Do a DFS carrying two things: the parent node and the current consecutive length.
- At each node, the length is
parent_length + 1if the value is exactlyparent.val + 1, otherwise reset to 1. - The answer is the maximum length seen anywhere.
- This is a top-down DP with no memoisation needed, since each node has a unique parent.
💻 Benchmark Python3 Implementation
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
def dfs(node: Optional[TreeNode], parent: Optional[TreeNode], length: int) -> int:
if not node:
return length
if parent and node.val == parent.val + 1:
length += 1 # extend the run
else:
length = 1 # restart
return max(length,
dfs(node.left, node, length),
dfs(node.right, node, length))
return dfs(root, None, 0)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): every node is visited once.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Comparing with
>=: the values must differ by exactly 1. - Passing the length without resetting: a broken run would keep accumulating.
- Allowing the path to go upward: consecutive paths must be strictly downward.
- Forgetting the
parent is Nonecase at the root: the root always starts a run of length 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.