⚡Flashcard Drill➔
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

  1. Do a DFS carrying two things: the parent node and the current consecutive length.
  2. At each node, the length is parent_length + 1 if the value is exactly parent.val + 1, otherwise reset to 1.
  3. The answer is the maximum length seen anywhere.
  4. 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 None case 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems