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

2025-03-13 HGNULB 约 4 分钟

文章信息 7 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决会员题 2-5 字节

题目描述

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

题意分析

在二叉树中寻找每走一步节点值恰好增加 1 的最长连续路径，长度按节点数计算。路径可以从任意节点开始、在任意节点结束，但只能从父节点走向子节点，不能折返经过父节点后连接左右两支。

解法：树形遍历递归处理

核心思路

[!blue]

每个非根节点只有一个父节点，因此以当前节点结尾的连续路径，能否延长只取决于父节点。递归传入父值 parentVal，以及以父节点结尾的最长连续长度 len。

若当前值等于 parentVal + 1，就把父节点的连续路径延长，长度为 len + 1；否则任何跨过这条父子边的路径都不连续，只能从当前节点重新开始，长度为 1。这个转移覆盖了以当前节点为终点的全部可能，因为不存在其他入边。

用 best 保存所有已访问节点的最大连续长度，每到一个节点就更新。最长段可能在内部节点结束，后续遇到不连续的值会重置局部长度，因此不能只在叶子处统计。再将当前值和当前长度分别传给两个孩子，两条分支只共享最终最大值，路径长度互不影响。

根节点传入长度 0，无论是否满足与初始父值的比较，最终都会得到长度 1；空节点直接返回，所以空树保留答案 0。Java 的 best 是成员字段，每次入口必须重置；比较时先转为 long 再加 1，避免最大 int 回绕后被误判为连续。

解题步骤

将 best 初始化为 0，从根节点和长度 0 开始递归。

当前节点为空则返回，否则比较当前值与父值加一。

连续时延长传入长度，不连续时将长度重置为 1。

更新 best，再把当前节点值和长度传给左右孩子。

遍历完成后返回 best。

代码实现

class Solution {
    private int best = 0;

    public int longestConsecutive(TreeNode root) {
        // 每次调用重新统计当前树，不继承此前的最大结果
        best = 0;
        dfs(root, 0, 0);

        return best;
    }

    // 传入长度截至父节点，当前节点决定延长还是从一重新开始
    private void dfs(TreeNode node, int parentVal, int len) {
        if (node == null) {
            return;
        }

        // 先转为宽整数再计算后继，不能把最大整数回绕当作递增
        if ((long) node.val == (long) 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)$，n 为节点数，每个节点只访问一次。

空间复杂度：$O(h)$，h 为树高，递归栈最深为一条根到叶路径；退化链时为 $O(n)$。

关键点总结

[!green]

全局最优与当前连续长度分开，断裂不清除历史最优。

长度在分支间按参数传递，左右互不污染。

易错点总结

[!yellow]

只在叶子更新，会漏掉中途结束的最长段。

重置为零会漏掉当前节点自己。

不清除上次调用结果，复用同一 Java 对象会返回旧答案。

窄整数先加一再比较，会把整数回绕错判为连续。

相似题目

题目	难度	关联与区别
549. 二叉树最长连续序列 II	中等	原题允许路径通过某个节点连接递增和递减两侧，本题只沿父到子递增1。
329. 矩阵中的最长递增路径	困难	同样记录以某点为起点的递增长度，本题在树上要求恰加1，原题网格只要求严格变大。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/33342683

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！