NeetCode #401LC-549MediumTreesNC Algo100
← Back to All Problems#401 · #549 · Binary Tree Longest Consecutive Sequence II(二叉树最长连续序列 II)
📌 Problem Statement & Constraints
Given the root of a binary tree, return the length of the longest consecutive path. Unlike the basic version, this path may be either increasing or decreasing, and it may turn at most once (a node can have one increasing and one decreasing branch). Constraints: the number of nodes is in
[1, 3 * 10^4].💡 Core Algorithmic Approaches
- For each node, compute two downward lengths: the longest increasing run starting at it and the longest decreasing run.
- A valid path through a node combines one increasing branch and one decreasing branch, giving
inc + dec - 1(the node itself is counted twice). - Track the maximum of that combination over all nodes.
- Each child contributes to at most one of the two counters, depending on whether its value is
node.val + 1ornode.val - 1.
💻 Benchmark Python3 Implementation
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
self.best = 0
def dfs(node: Optional[TreeNode]):
"""Return (longest increasing downward run, longest decreasing downward run)."""
if not node:
return (0, 0)
inc = dec = 1
if node.left:
l_inc, l_dec = dfs(node.left)
if node.left.val == node.val + 1:
inc = max(inc, l_inc + 1)
elif node.left.val == node.val - 1:
dec = max(dec, l_dec + 1)
if node.right:
r_inc, r_dec = dfs(node.right)
if node.right.val == node.val + 1:
inc = max(inc, r_inc + 1)
elif node.right.val == node.val - 1:
dec = max(dec, r_dec + 1)
# a path through this node: one increasing + one decreasing branch
self.best = max(self.best, inc + dec - 1)
return (inc, dec)
dfs(root)
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one post-order traversal.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Returning a single length: both directions must be propagated so the parent can combine them.
- Forgetting the
-1ininc + dec - 1: the current node is counted in both runs. - Allowing both branches to be increasing: a path may turn only once, so one branch must increase and the other decrease.
- Comparing with a difference other than 1: the values must be exactly consecutive.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.