LeetCode 549. 二叉树最长连续序列 II
题目描述
题意分析
求二叉树中最长连续整数路径的节点数。路径可以先从子节点走向父节点，再走到另一分支，但数值沿整条路径必须始终每步加一，或始终每步减一。
任意路径都有一个在树中离根最近的节点，路径可以在这里连接两条向下的链。为了判断两条链能否接成同一个连续方向，需要分别保留从当前节点向下递增和递减的最长长度。
解法：DFS 返回上升/下降长度
核心思路
[!blue]
向上只返回单方向链，本地合成拐点路径。inc、dec分别表示从当前节点开始向下、每步加一或减一的最长链，长度都包含当前节点，初值为一。先递归获得孩子的两种状态；若孩子值比当前值大一，就用孩子的inc+1更新当前inc，若小一则用孩子的dec+1更新当前dec。值差不符时，不能通过这条边延伸。合并时，将向下递减链反向走到当前节点，再沿向下递增链继续，整条路径就始终每步加一；反过来走则始终减一。因此以当前节点为结构上最高点的最长路径为
inc+dec-1，减一是因为当前节点被两种长度各计算了一次。当两条链都长于一时，它们一定来自不同孩子，因为同一孩子的值不可能既比父节点大一又小一；所以合并不会重复走进同一分支。若其中一条长度为一，合并结果就退化为另一条单链，同样合法。
每条路径的结构最高点都会被遍历到，在每个节点用合并长度更新
answer就能覆盖全树最优解。向父层只返回inc、dec两种单链长度，不能返回合并后的路径，否则父层再接入会形成分叉，而非一条简单路径。
解题步骤
- 空节点返回零长度。
- 后序计算左右孩子的递增、递减长度。
- 按父子值差分别更新当前两类链。
- 合并更新答案，并返回单向状态。
代码实现
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)$，每个节点处理一次。
- 空间复杂度：$O(h)$，递归栈由树高决定。
关键点总结
[!green]
- 递增接递增，递减接递减，方向不能丢失。
- 合并路径只在当前节点结算，父层接收单向链。
- 答案可能位于任意子树，不一定经过根。
易错点总结
[!yellow]
- 只看差的绝对值而不区分方向：可能拼出先升后降的非法序列。
- 合并不减一：根节点被重复计数。
- 只在整棵树根更新答案：漏掉子树内部更长路径。
- 把合并后的长度作为单链返回：可能重复经过拐点形成不存在的路径。
- 节点值相等不能延伸连续链；只有一个节点时两种长度都是一，合并后答案也为一。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 298. 二叉树最长连续序列 | 中等 | 原题只允许父到子递增路径，本题还可在某节点连接递增与递减两条分支。 |
| 543. 二叉树的直径 | 简单 | 同样在节点处合并左右臂，本题两臂还必须分别满足数值连续方向。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！