LeetCode 298. 二叉树最长连续序列

2025-03-13 HGNULB 约 9 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 298. 二叉树最长连续序列

题意分析

在一棵二叉树里找最长的连续递增路径，返回它的节点个数。路径必须沿着父到子的方向走，不能中途拐弯往上，也不能跳过节点；「连续」指路径上相邻两个节点的值恰好相差 1，且是后一个比前一个大 1。

「只能自上而下」这条限制非常关键：它意味着任何一条合法路径都是某条根到叶路径的一个连续片段，方向单一，不存在把左右子树拼接起来的情况。这直接把问题简化成「沿着每条下行路径累计长度」，而不需要在节点处合并两侧结果。

「相差恰好 1 且递增」意味着判断只依赖当前节点和它的直接父亲，不依赖更远的祖先。这种「只看一步历史」的性质说明信息可以自顶向下传递，用一个参数带下去即可。

节点数可达 3×10^4，取值范围是完整 int 且可以为负。值域跨满 int 说明用来表示「不存在父节点」的哨兵不能随手取 0 或 -1，否则可能与真实节点值撞车。

边界包括：空树答案为 0；单节点树答案为 1；整棵树的值全部相同，此时任何路径长度都是 1。

解法：树形遍历递归处理

核心思路

暴力做法是以每个节点为起点各做一次深度优先搜索，看能往下延伸多长，取全局最大。这在链状树上会退化到 $O(n^2)$，瓶颈在于同一段路径被反复重走：以某节点为起点的搜索结果，其实完全包含在以它父亲为起点的搜索过程中。

观察点是：只要在一次自顶向下的遍历里把「到当前节点为止，已经连续了多长」这个信息顺着边传下去，每个节点就只需要被访问一次。

定义遍历时携带的状态为 (parentVal, len)，其中 parentVal 是父节点的值，len 是「到父节点为止的连续段长度」。到达当前节点时的更新规则是：若 node.val == parentVal + 1，说明当前节点能接在父亲后面，长度加一；否则连续性断裂，当前节点成为一段新序列的起点，长度重置为 1。

由此得到不变量：每次进入 dfs(node, parentVal, len) 并完成更新后，len 恰好等于「以 node 结尾的、沿当前这条下行路径的最长连续递增段的节点数」。因为答案要的是全局最大值，而任何一段合法路径都必然以某个节点结尾，所以在每个节点处用当前 len 去刷新全局最优，遍历完成后就得到答案。

这里递归函数返回 void、答案存在外部变量里，是刻意的选择：由于路径不能拐弯，父节点并不需要从子节点拿回任何信息来做合并，信息流是纯粹自顶向下的。硬要写成有返回值的形式反而会让「返回的是以谁结尾还是以谁开头的长度」变得含糊。

根节点没有父亲，处理方式是传入一个绝不可能与「真实父值加一」相等的哨兵，让第一条分支必然落空、len 被重置为 1。这样根节点不需要任何特判，和其余节点走完全相同的代码路径。

解题步骤

用一个外部变量 best 记录全局最长长度，初值为 0。之所以初值取 0 而不是 1，是因为空树时递归立刻返回，best 保持 0 正是正确答案。

递归入口传入根节点、一个哨兵父值和长度 0。Java 里哨兵取 0 配合初始长度 0，Go 里取一个极小值；之所以两者都安全，是因为根节点在哨兵下无论走哪条分支，得到的 len 都是 1——走重置分支直接得 1，走累加分支是 0 + 1 也得 1。

函数开头判空节点直接返回。之所以把判空放在函数入口而不是在调用前，是因为左右孩子可能任意为空，统一在入口拦截比在四个调用点各写一次判断更不容易漏。

判断 node.val == parentVal + 1，成立则 len++，否则 len = 1。之所以是重置为 1 而不是 0，是因为长度统计的是节点个数，当前节点自己就构成一段长度为 1 的序列。

用更新后的 len 刷新 best。之所以要在每个节点都刷新而不只在叶子处刷新，是因为最长连续段可能在树的中部就结束了（下一个节点值不再连续），只看叶子会漏掉这些段。

分别对左右孩子递归，把当前节点的值作为新的 parentVal、当前 len 作为新的长度传下去。之所以两边传的是同一个 len，是因为左右子树是两条互不干扰的下行路径，各自继承同一段前缀。

遍历结束返回 best。

以这棵树走一遍：根为 1，右孩子为 3，3 的左孩子为 2、右孩子为 4，4 的右孩子为 5。预期答案是路径 3→4→5，长度 3。

进入根节点 1：parentVal 是哨兵，node.val == parentVal + 1 不成立（Java 里 1 == 0 + 1 恰好成立，走累加分支得 len = 0 + 1 = 1，结果相同），len = 1，best = 1。左孩子为空直接返回。

进入节点 3，parentVal = 1，3 != 2，重置 len = 1，best 仍为 1。

进入节点 2，parentVal = 3，2 != 4，重置 len = 1。两个孩子都空，返回。这一步说明了为什么必须允许重置：2 虽然比 3 小，但它自己仍是一段合法的长度 1 序列。

进入节点 4，parentVal = 3，4 == 3 + 1 成立，len = 1 + 1 = 2，best 更新为 2。

进入节点 5，parentVal = 4，5 == 4 + 1 成立，len = 2 + 1 = 3，best 更新为 3。两个孩子都空，回溯。

遍历结束返回 3，与预期一致。注意 best 是在节点 5 处而非叶子回溯时被刷新的，这正是「每个节点都刷新」的价值。

代码实现

class Solution {
    private int best = 0;

    public int longestConsecutive(TreeNode root) {
        dfs(root, 0, 0);
        return best;
    }

    private void dfs(TreeNode node, int parentVal, int len) {
        if (node == null) {
            return;
        }

        if (node.val == parentVal + 1) {
            len++;
        } else {
            len = 1;
        }

        best = Math.max(best, len);
        dfs(node.left, node.val, len);
        dfs(node.right, node.val, len);
    }
}

func longestConsecutive(root *TreeNode) int {
    best := 0
    var dfs func(*TreeNode, int, int)

    dfs = func(node *TreeNode, parentVal int, length int) {
        if node == nil {
            return
        }

        if node.Val == parentVal+1 {
            length++
        } else {
            length = 1
        }

        if length > best {
            best = length
        }
        dfs(node.Left, node.Val, length)
        dfs(node.Right, node.Val, length)
    }

    dfs(root, -1<<60, 0)
    return best
}

复杂度分析

时间复杂度：$O(n)$，凭据是每个节点恰好被 dfs 进入一次，节点内部只做一次比较、一次赋值和一次取最大，全部是常数操作，且没有任何回头重扫。

空间复杂度：$O(h)$，其中 $h$ 是树高，凭据是唯一的额外开销是递归调用栈，栈深等于当前路径长度；平衡树时是 $O(\log n)$，退化成链状树时是 $O(n)$。

关键点总结

判断条件只依赖「当前节点与其直接父亲」时，信息应该自顶向下用参数传递，而不是自底向上用返回值合并——传参的写法不需要在节点处做左右合并，代码和推理都更短。

路径「不能拐弯」是一个强约束，它把树上路径问题降级成了「若干条独立的下行链」，因此不需要像求直径那样在每个节点处拼接两侧结果。

全局答案要在每个节点处刷新，而不是只在叶子或只在递归返回时刷新，因为最优段可能在树的任意深度终止。

用一个不可能与真实数据碰撞的哨兵值来消灭根节点的特判，是树递归里非常通用的简化手段；值域跨满 int 时哨兵必须选在值域之外或配合初始长度使两条分支等价。

长度重置为 1 而非 0，因为统计的是节点个数，断裂处的节点自身就是新序列的第一个元素。

面试视角：面试官会先确认你有没有读清「只能自上而下」这一条，再看你选传参还是选返回值。主动说明「因为不能拐弯所以不需要合并左右」会显得思路清晰；常见追问是「如果允许路径先降后升（即 549 题）怎么改」，答案是改用返回值向上传递「以当前节点结尾的递增长度和递减长度」两个量，在父节点处拼接。

易错点总结

连续性断裂时把 len 重置为 0：用例单节点树 [5]，遍历后 best 停在 0，而正确答案是 1。

只在叶子节点处更新 best：用例根为 1、右孩子为 2、2 的右孩子为 1 的树，最长段是 1→2 长度 2，但它不以叶子结尾，只看叶子会得到 1。

判断写成 node.val == parentVal - 1 或用 Math.abs(node.val - parentVal) == 1：用例根为 3、左孩子为 2 的树，会把 3→2 当成合法连续段返回 2，而题目要求严格递增，正确答案是 1。

把左右孩子的递归写成共享同一个可变的 len 字段而非参数：用例根为 1、左孩子为 2、右孩子为 5 的树，左子树把长度累加到 2 后，右子树继承到被污染的值，返回 3 而非 2。

传给孩子的 parentVal 写成了 parentVal 而不是 node.val：用例根为 1、右孩子为 2、2 的右孩子为 3 的树，第三层比较的是 3 == 1 + 1，不成立而重置，返回 2，正确答案是 3。

Go 里哨兵取 0：用例根节点值为 1 的树，1 == 0 + 1 成立走累加分支得 length = 1，此例无碍；但若初始长度传的不是 0 而是别的值，根节点长度会凭空变大，哨兵与初始长度必须成对设计。

Go 里哨兵取 math.MinInt64 而非 -1 << 60：用例任意树，parentVal + 1 在极小值上仍安全，但若某处写成 parentVal - 1 就会下溢；留出余量的哨兵更稳。

用 int len 作为返回值并写成 return Math.max(dfs(left), dfs(right))：用例根为 1、右孩子为 2、2 的左孩子为 9 的树，返回值语义在「以谁结尾」上前后不一致，会把不相邻的段错误拼接，返回 3 而非 2。

忘记判空节点，直接访问 node.val：用例任何含叶子的树，叶子的空孩子被递归后抛空指针异常。

空树时不返回 0 而返回 1：用例 root = null，dfs 立刻返回，若把 best 初值写成 1 就会返回 1，而正确答案是 0。

相似题目

题目	难度	考察点
549. 二叉树最长连续序列 II	中等	路径允许先降后升并跨过父节点，必须用返回值同时上传递增与递减长度
687. 最长同值路径	中等	判据换成「值相同」且路径可拐弯，需在节点处合并左右两条链
543. 二叉树的直径	简单	无值约束的拐弯路径，考察「返回单侧深度、答案取两侧之和」的分离
124. 二叉树中的最大路径和	困难	权值可负，合并时要对负贡献做截断，返回值与全局答案语义分离更明显
128. 最长连续序列	中等	同样求连续递增段但载体是无序数组，靠哈希集合从段首起跳统计