LeetCode 549. 二叉树最长连续序列 II
目录
题目描述
题意分析
在一棵二叉树里找一条最长的路径，要求路径上的节点值构成连续整数序列（相邻两个节点的值相差恰好 1），返回这条路径的节点个数。与前一题（298 题）不同的是，这里的路径不必自顶向下：它可以先沿着某条边向上走到某个祖先，再拐下去走另一条分支；同时序列既可以递增也可以递减，只要方向在整条路径上保持一致即可。
「可以拐弯」这四个字是全部难点所在。一旦允许拐弯，路径就不再是「某个节点到它某个后代」的直链，而是「以某个节点为最高点、向左右各伸出一条腿」的 V 字形。而值必须连续单调，意味着从最高点看出去：一条腿必须是递增下去的，另一条腿必须是递减下去的——只有这样，把递减那条腿反过来读，整条路径才是一路递增。
由此确定了枚举方式：每个节点都可能是那个拐点，答案就是所有拐点方案里的最大值。这也解释了为什么单纯记录一个方向的链长不够——每个节点必须同时知道自己「向下递增能走多远」和「向下递减能走多远」两个量。
约束方面，树的节点数是线性规模，说明目标是一趟遍历 $O(n)$；任何「对每个节点都重新往下搜一遍」的 $O(n^2)$ 做法都不是期待的答案。节点值可以为负、也可以重复出现，所以判断连续必须用严格的
+1/-1相等判断，不能用差的绝对值等于 1 来含糊处理（那样会把方向弄丢）。边界：空树返回
0；单个节点本身就是长度为1的合法序列；父子值相等时既不算递增也不算递减，链在此断开，双方都从1重新起算。
解法：DFS 返回上升/下降长度
核心思路
先看暴力：以每个节点为拐点，分别向左右子树做一次深搜，找出最长的递增腿和最长的递减腿。这样每个节点都要遍历一次自己的子树，总复杂度 $O(n^2)$（链状树时退化明显），而且左右两次搜索里大量子问题被重复求解。
瓶颈显而易见：同一棵子树被它的每个祖先各搜了一遍。而仔细看会发现，某个节点的「向下递增最长链」这个量，只依赖它自己和它两个孩子的同名量——是一个可以自底向上一次算完的量。于是把它做成后序遍历的返回值，每个节点只算一次。
定义两个状态，注意都以当前节点为起点、一路向下：
inc(node)= 从node出发向下走，值每步加 1 的最长路径节点数；dec(node)= 从node出发向下走，值每步减 1 的最长路径节点数。两者最小值都是1（就是节点自己）。转移写出来是：对每个非空孩子
c，若c.val == node.val + 1，则inc(node)可以取inc(c) + 1；若c.val == node.val - 1，则dec(node)可以取dec(c) + 1；两个孩子各算一遍取最大。注意这两个条件天然互斥——一个孩子的值不可能同时是node.val + 1和node.val - 1，所以写else if是安全的。答案的合成在每个节点处完成：以
node为拐点的最长连续路径 =inc(node) + dec(node) - 1。为什么减 1？因为两条腿都把node自己算进去了，合并时重复了一次。这个式子同时覆盖了三种形态：只有一条递增腿（dec = 1）、只有一条递减腿（inc = 1）、以及真正的 V 字形。这里有个容易被忽略但至关重要的正确性论证：
inc和dec若都大于 1，它们必然来自不同的孩子，所以拼起来是一条合法的简单路径，不会重复经过同一个节点。理由就是上面那条互斥性——同一个孩子只能贡献给inc和dec其中之一。用一个全局变量在后序遍历中不断打擂台记录最大值，遍历结束即为答案。返回值只负责向上传递两条腿的长度，答案的合成留在本地——这是所有「路径可拐弯」类树形 DP 的通用范式（124 题、543 题同理）。
解题步骤
- 准备一个全局答案
answer = 0，写一个后序 DFS，返回(inc, dec)二元组。为什么：返回值和答案是两套不同的口径——返回的是「从我出发向下的单向链」，供父节点继续拼接；答案是「以我为拐点的完整路径」，无法向上传递（拐点路径接不到父亲上），只能就地记录。混淆这两者是本题最根本的错误。- 空节点返回
(0, 0)。为什么：返回0而不是1，是因为空节点不贡献任何节点数；不过下面的代码并不依赖这个返回值——真正拦住空孩子的是node.left != null的判断，返回(0, 0)只是让递归有个安全的出口。- 非空节点先令
inc = 1, dec = 1。为什么：节点自己就是一条长度为 1 的合法链，这是所有转移的下界；用它作初值，叶子节点和「孩子值不连续」的情况都不需要额外分支。- 递归左孩子，若左孩子非空，按值关系更新：
left.val == node.val + 1时inc = max(inc, leftInc + 1)；left.val == node.val - 1时dec = max(dec, leftDec + 1)。为什么：必须用孩子的同向状态接上——递增链要接孩子的inc，接dec就把方向拧断了；+1是把当前节点算进去；两个条件互斥所以用else if，值相等或相差大于 1 时两个分支都不进，链自然从1重新起算。- 对右孩子重复同样的处理。为什么：两条腿可能分别来自左右孩子，也可能同一侧孩子同时是两个方向的更优来源之一；对两侧都跑一遍并取
max，才能覆盖所有情况。- 更新
answer = max(answer, inc + dec - 1)。为什么：这一步必须在两个孩子都处理完之后做，此时inc与dec才是最终值；减 1 是去掉node被两条腿各算一次的重复。- 返回
(inc, dec)。为什么：父节点只关心「从我这里能不能继续单向延伸」，拐点信息已经在本地结算过了。以树
[2, 1, 3]（根2，左孩子1，右孩子3）走一遍。后序先到左孩子
1：它是叶子，inc = dec = 1，更新answer = max(0, 1 + 1 - 1) = 1，返回(1, 1)。再到右孩子
3：同样是叶子，返回(1, 1)，answer仍是1。回到根
2：初值inc = dec = 1。看左孩子，1 == 2 - 1成立，走dec分支，dec = max(1, 1 + 1) = 2。看右孩子，3 == 2 + 1成立，走inc分支，inc = max(1, 1 + 1) = 2。更新answer = max(1, 2 + 2 - 1) = 3。返回(2, 2)。最终答案
3，对应路径1 → 2 → 3——它先从左孩子向上走到根，再拐下去到右孩子，正是本题相对 298 题新增的「拐弯」形态。注意根节点的dec = 2来自左孩子、inc = 2来自右孩子，两条腿分处两侧，拼起来是一条不重复经过节点的合法路径。再看一个反例式的细节：若把右孩子的值改成
2（与根相等），则右孩子既不满足+1也不满足-1，两个分支都不进，根的inc保持1，answer = max(1, 1 + 2 - 1) = 2，对应路径1 → 2。这说明「值相等」必须被当作断点，而不是当作连续。
代码实现
class Solution {
private int answer;
public int longestConsecutive(TreeNode root) {
answer = 0;
dfs(root);
return answer;
}
// 返回 {inc, dec}：从 node 向下的最长递增链、最长递减链的节点数。
private int[] dfs(TreeNode node) {
if (node == null) {
return new int[]{0, 0};
}
// 节点自身就是长度为 1 的合法链，作为所有转移的下界。
int inc = 1;
int dec = 1;
int[] left = dfs(node.left);
if (node.left != null) {
// 递增链只能接孩子的递增链，两个条件天然互斥。
if (node.left.val == node.val + 1) {
inc = Math.max(inc, left[0] + 1);
} else if (node.left.val == node.val - 1) {
dec = Math.max(dec, left[1] + 1);
}
}
int[] right = dfs(node.right);
if (node.right != null) {
if (node.right.val == node.val + 1) {
inc = Math.max(inc, right[0] + 1);
} else if (node.right.val == node.val - 1) {
dec = Math.max(dec, right[1] + 1);
}
}
// 以 node 为拐点：两条腿都算了自己一次，合并时减 1。
answer = Math.max(answer, inc + dec - 1);
return new int[]{inc, dec};
}
}
func longestConsecutive(root *TreeNode) int {
answer := 0
// 返回 (inc, dec)：从 node 向下的最长递增链、最长递减链的节点数。
var dfs func(node *TreeNode) (int, int)
dfs = func(node *TreeNode) (int, int) {
if node == nil {
return 0, 0
}
// 节点自身就是长度为 1 的合法链，作为所有转移的下界。
inc, dec := 1, 1
li, ld := dfs(node.Left)
if node.Left != nil {
// 递增链只能接孩子的递增链，两个条件天然互斥。
if node.Left.Val == node.Val+1 {
if li+1 > inc {
inc = li + 1
}
} else if node.Left.Val == node.Val-1 {
if ld+1 > dec {
dec = ld + 1
}
}
}
ri, rd := dfs(node.Right)
if node.Right != nil {
if node.Right.Val == node.Val+1 {
if ri+1 > inc {
inc = ri + 1
}
} else if node.Right.Val == node.Val-1 {
if rd+1 > dec {
dec = rd + 1
}
}
}
// 以 node 为拐点：两条腿都算了自己一次，合并时减 1。
if inc+dec-1 > answer {
answer = inc + dec - 1
}
return inc, dec
}
dfs(root)
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，
n为节点数。凭什么：每个节点在后序遍历中被访问且仅被访问一次，节点内部只做常数次比较与取最大；答案的合成也在节点内就地完成，没有任何二次遍历。- 空间复杂度：$O(h)$，
h为树高，最坏 $O(n)$。凭什么：唯一的额外开销是递归调用栈，深度等于树高；链状树时h = n，完全平衡时h = \log n。每层只保存两个int（Java 版为一个长度 2 的数组），是常数。
关键点总结
- 「路径可以拐弯」是一个强信号：立刻想到「枚举每个节点作为路径最高点，向左右各取一条腿」的树形 DP 范式。124 题（最大路径和）、543 题（直径）与本题是同一个模子刻出来的。
- 分清「向上返回的量」和「就地结算的答案」是这个范式的命门。返回值必须是能被父节点继续拼接的单向链，拐点路径接不上父亲，只能用全局变量记录。面试时把这句话讲明白，基本就过了。
- 单调方向不能丢。递增链只能接孩子的递增链、递减链只能接孩子的递减链，接反了会拼出先升后降再升的非法序列。
- 一个节点需要几个状态，取决于「向上拼接时父亲需要知道什么」。本题父亲既可能比我大 1 也可能比我小 1，所以必须同时返回两个方向的长度。
- 正确性依赖一条隐含论证：
inc与dec的来源孩子必然不同（因为一个孩子的值不能同时是+1和-1），所以拼接结果一定是简单路径。能主动补上这句证明，是从「会写」到「懂了」的分界。- 用严格的
== val + 1/== val - 1判断，而不是abs(diff) == 1。后者虽然也能识别相邻，却丢掉了方向信息，无法决定该接inc还是dec。
易错点总结
- 用
Math.abs(child.val - node.val) == 1判断连续：树[2, 1, 1]（根2，两个孩子都是1）→ 两个孩子都被同时算进inc和dec，得出1 + 2 - 1甚至更大的错误结果，实际答案是2。- 递增链接了孩子的
dec（或反之）：树[1, 2, null, null, 1]（1 → 2 → 1）→ 会把先升后降的折线当成连续序列，返回3，正确答案是2。- 把
inc + dec - 1作为返回值传给父节点：树[2, 1, 3]的父层拿到3后继续加 1 → 拼出根本不存在的路径，答案越算越大。返回值必须只含单向链长。- 忘记减 1：树
[2, 1, 3]→ 得到2 + 2 = 4，比实际路径1 → 2 → 3的3个节点多了一个，因为根被算了两次。- 只在根节点更新答案：树的最长连续序列出现在某棵子树内部（如根值为
100、左子树是1 → 2 → 3）→ 根处的inc + dec - 1只有1，答案错报为1。答案必须在每个节点都打擂台。inc、dec初值写成0：任意单节点树 → 答案算成0 + 0 - 1 = -1，返回负数；正确答案是1。- 空节点返回
(1, 1)：叶子节点会误以为自己有一个长度为 1 的孩子链 → 若同时去掉node.left != null的判断，叶子会算出inc = 2，全树答案整体偏大。- 漏掉
node.left != null/node.right != null的判断：直接访问node.left.val→ 叶子节点处空指针异常。- 答案更新写在处理右孩子之前：树
[2, 1, 3]→ 结算时inc还是1，得到1 + 2 - 1 = 2，漏掉了右腿，正确答案是3。- 值相等时仍延续链条：树
[1, 1, 1]→ 把等值当成连续，返回3，正确答案是1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 298. 二叉树最长连续序列 | 中等 | 路径必须自顶向下且只能递增，只需一个状态、无需拐点合并 |
| 124. 二叉树中的最大路径和 | 困难 | 同为拐点合并，但腿长可为负要与 0 取舍，权衡在于「这条腿要不要」 |
| 543. 二叉树的直径 | 简单 | 拐点合并的最简形态，两条腿无任何值约束，直接取左右深度之和 |
| 687. 最长同值路径 | 中等 | 约束从「差 1」变成「相等」，方向消失所以只需一个状态 |
| 1372. 二叉树中的最长交错路径 | 中等 | 状态同样是两个，但区分的是「上一步走左还是走右」而非值的升降 |
| 128. 最长连续序列 | 中等 | 同样求连续整数，但载体是无序数组，靠哈希集合找序列起点而非树结构 |
| 437. 路径总和 III | 中等 | 路径仍须自顶向下但起点任意，用前缀和加哈希表统计而非返回链长 |
| 1120. 子树的最大平均值 | 中等 | 同为后序返回多元组（和与节点数），但结算对象是整棵子树而非路径 |