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

  1. For each node, compute two downward lengths: the longest increasing run starting at it and the longest decreasing run.
  2. A valid path through a node combines one increasing branch and one decreasing branch, giving inc + dec - 1 (the node itself is counted twice).
  3. Track the maximum of that combination over all nodes.
  4. Each child contributes to at most one of the two counters, depending on whether its value is node.val + 1 or node.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 -1 in inc + 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems

中文速览与面试要点

二叉树最长连续序列 II

给定二叉树的根节点 root,返回树中 最长连续序列路径 的长度。路径可以在任意节点开始和结束,且路径可以经过父节点和子节点,但 只能 沿着父节点到子节点的方向。路径可以是 递增 的,也可以是 递减 的,甚至可以 先递增后递减 (即路径上存在一个峰值)。约束:树中节点数目在范围 [1, 3 × 10^4] 内;-3 × 10^4 ≤ Node.val ≤ 3 × 10^4。

核心要点

  • 树形 DP 返回二元组(标准解) :递归函数返回 (以当前节点为端点的最长递增序列长度, 最长递减序列长度) 。
  • 状态转移 :对每个子节点,若 子.val == node.val + 1 则递增长度可取 子.inc + 1 ;若 子.val == node.val − 1 则递减长度可取 子.dec + 1 。左右子树分别更新,取最大值。
  • 全局最优 :经过当前节点的「先增后减」路径长度为 inc + dec − 1 (当前节点被算了两次),用它更新全局最优。
  • 为什么用二元组 :父节点需要知道「子节点的递增/递减延伸长度」才能判断能否接上,因此必须返回两个方向的信息。

常见陷阱

  • 全局最优写成 inc + dec :当前节点被算了两次,必须减 1。
  • 只返回一个方向 :父节点无法判断另一方向能否接上,会漏解。必须返回二元组。
  • 条件用 == 之外的关系 :必须严格相差 1( node.val + 1 或 node.val − 1 )。
  • inc / dec 初值设为 0 :只含当前节点的路径长度为 1,初值应为 1。
  • 与 298 混淆 :298 只允许单向递增且路径必须向下延伸;本题允许折线。

参考实现

class Solution:
    def longestConsecutive(self, root: 'TreeNode') -> int:
        best = 0

        def dfs(node):
            """返回 (以 node 为端点的最长递增长度, 最长递减长度)。"""
            nonlocal best
            if not node:
                return (0, 0)
            inc = dec = 1                       # 只含当前节点

            l_inc, l_dec = dfs(node.left)
            r_inc, r_dec = dfs(node.right)

            if 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:
                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)

            # 经过 node 的折线路径(先增后减),node 被算了两次
            if inc + dec - 1 > best:
                best = inc + dec - 1
            return (inc, dec)

        dfs(root)
        return best