二叉树最长连续序列 II（LeetCode 549）：双状态后序 DFS 完整解法指南

二叉树最长连续序列 IILeetCode 549双状态后序 DFS 完整解法指南【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文讲解 LeetCode 549「二叉树最长连续序列 II」Binary Tree Longest Consecutive Sequence II的完整解题思路核心目标是在任意二叉树中寻找最长连续路径——与第 I 题只允许「父 → 子」单向递增不同本题允许路径在任意节点处转弯即可以从某个子树沿递减方向走到转折点再沿递增方向进入另一个子树。读完本文你将掌握暴力枚举方案的复杂度瓶颈、单次遍历中同时维护「递增长度 / 递减长度」双状态的多状态 DFS 技巧、inr dcr - 1去重公式的推导以及 Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust 九种语言的实现对照。本仓库中的讲解文档 binary-tree-longest-consecutive-sequence.md 与 binary-tree-longest-consecutive-sequence-ii.md 构成该题型的 I / II 两篇完整教程。1. 问题回顾与前置知识1.1 与第 I 题的关键差异LeetCode 298「二叉树最长连续序列」Binary Tree Longest Consecutive Sequence要求路径只能自上而下严格递增即每个子节点的值恰好等于父节点值加 1而本题549放宽了约束路径中的相邻节点值之差必须为 1方向既可以递增也可以递减路径可以在任意节点处改变方向从递减转为递增反之亦然。例如一棵树中1 → 2 → 3是一条递增连续路径3 → 2 → 1是一条递减连续路径而1 → 2 → 3 → 2 → 1这类「先递增后递减」的路径在第 I 题中不被允许但在第 II 题中完全合法。因此在求解前建议先掌握第 I 题的两种 DFS 思路见仓库文档 binary-tree-longest-consecutive-sequence.md该文详细讲解了自上而下传参和自下而上返回长度的两种做法。1.2 本题需要的前置能力在动手写代码前应确保自己对以下内容足够熟练二叉树结构理解节点如何通过 left 和 right 子指针相连深度优先搜索DFS递归遍历树并从子树返回计算好的值多状态返回值在每个节点同时追踪多条信息如递增长度 / 递减长度路径组合逻辑将左右子树的路径通过公共节点拼接合并。2. 暴力解法会超时仅供思路热身2.1 直觉暴力解法的出发点是既然最长连续路径可能在树中任意位置、以任意方向出现那就枚举树中所有可能的路径逐一验证其节点值是否构成连续序列递增或递减差 1。对每个节点把它视为潜在路径的组成部分枚举其左、右子树中所有可能的起点和终点组合从而覆盖所有「经过该节点」的路径对每条路径检查值是否连续并持续追踪全局最大长度。2.2 算法步骤遍历树中的每个节点把它当作潜在连续路径的一部分枚举所有包含该节点的路径即组合左、右子树中节点的各种起止点对每条路径验证节点值是否构成连续序列递增或递减差 1在所有合法连续路径中记录最大长度。2.3 时间复杂度与空间复杂度时间复杂度$O(n^3)$空间复杂度$O(n^3)$其中 $n$ 为输入树的节点数。从复杂度即可看出枚举全部路径的代价是立方的在稍大的树如节点数达到数千上必然超时。它存在的意义只是帮助理解「为什么需要单次遍历方案」。3. 单次遍历双状态后序 DFS最优解3.1 核心直觉一次遍历找到答案的关键在于每个节点同时向下追踪两条信息——「从当前节点出发、沿子节点方向的最长递增路径长度」和「从当前节点出发、沿子节点方向的最长递减路径长度」。为什么需要两条信息因为路径可以在某个节点处转弯一条从左侧子树沿递增方向延伸过来的路径与一条从右侧子树沿递减方向延伸过来的路径恰好可以在当前节点汇合拼成一条完整的连续序列。于是在每个节点处把这两条长度相加再减 1 去掉重复计数的当前节点就能得到「经过该节点的最长路径」。对所有节点取最大值即为全局答案。换个角度理解方向命名的易混点站在父节点视角若child.val parent.val - 1说明父节点可以接在子节点的递增路径之后若child.val parent.val 1说明父节点可以接在子节点的递减路径之后。文档中的inrincreasing与dcrdecreasing正是分别记录这两种向下延伸长度的变量。3.2 算法步骤初始化一个全局变量maxval保存最大路径长度定义 DFS 函数返回一个二元组[递增长度, 递减长度]表示「从当前节点出发向下」的最长递增 / 递减连续路径长度若当前节点为null返回[0, 0]初始时递增、递减长度都设为1仅包含当前节点自己处理左子节点若其存在且与当前节点构成连续关系值差 1则按方向扩展对应长度处理右子节点同样按方向扩展并与左子节点得到的长度取最大值用inr dcr - 1更新全局最大值——当前节点在两条路径中被重复计数了一次必须减 1返回[inr, dcr]供父节点继续使用。3.3 为什么必须对左右子节点分别取最大值一个常见的错误想法是「左子树贡献递增、右子树贡献递减」。实际上左右子节点对两个方向都可能做出贡献当root.val root.left.val - 1时左子扩展递增当root.val root.left.val 1时左子扩展递减右子同理。因此在每个方向上都应对左右两棵子树的候选长度取max而非固定分配方向。3.4 各语言实现::tabs-startclass Solution: def longestConsecutive(self, root: TreeNode) - int: def longest_path(root: TreeNode) - List[int]: nonlocal maxval if not root: return [0, 0] inr dcr 1 if root.left: left longest_path(root.left) if (root.val root.left.val 1): dcr left[1] 1 elif (root.val root.left.val - 1): inr left[0] 1 if root.right: right longest_path(root.right) if (root.val root.right.val 1): dcr max(dcr, right[1] 1) elif (root.val root.right.val - 1): inr max(inr, right[0] 1) maxval max(maxval, dcr inr - 1) return [inr, dcr] maxval 0 longest_path(root) return maxvalclass Solution { int maxval 0; public int longestConsecutive(TreeNode root) { longestPath(root); return maxval; } public int[] longestPath(TreeNode root) { if (root null) { return new int[] {0,0}; } int inr 1, dcr 1; if (root.left ! null) { int[] left longestPath(root.left); if (root.val root.left.val 1) { dcr left[1] 1; } else if (root.val root.left.val - 1) { inr left[0] 1; } } if (root.right ! null) { int[] right longestPath(root.right); if (root.val root.right.val 1) { dcr Math.max(dcr, right[1] 1); } else if (root.val root.right.val - 1) { inr Math.max(inr, right[0] 1); } } maxval Math.max(maxval, dcr inr - 1); return new int[] {inr, dcr}; } }class Solution { private: int maxval 0; vectorint longestPath(TreeNode* root) { if (root nullptr) { return {0, 0}; } int inr 1, dcr 1; if (root-left ! nullptr) { vectorint left longestPath(root-left); if (root-val root-left-val 1) { dcr left[1] 1; } else if (root-val root-left-val - 1) { inr left[0] 1; } } if (root-right ! nullptr) { vectorint right longestPath(root-right); if (root-val root-right-val 1) { dcr max(dcr, right[1] 1); } else if (root-val root-right-val - 1) { inr max(inr, right[0] 1); } } maxval max(maxval, dcr inr - 1); return {inr, dcr}; } public: int longestConsecutive(TreeNode* root) { longestPath(root); return maxval; } };class Solution { constructor() { this.maxval 0; } /** * param {TreeNode} root * return {number} */ longestConsecutive(root) { this.maxval 0; this.longestPath(root); return this.maxval; } /** * param {TreeNode} root * return {number[]} */ longestPath(root) { if (root null) { return [0, 0]; } let inr 1, dcr 1; if (root.left ! null) { let left this.longestPath(root.left); if (root.val root.left.val 1) { dcr left[1] 1; } else if (root.val root.left.val - 1) { inr left[0] 1; } } if (root.right ! null) { let right this.longestPath(root.right); if (root.val root.right.val 1) { dcr Math.max(dcr, right[1] 1); } else if (root.val root.right.val - 1) { inr Math.max(inr, right[0] 1); } } this.maxval Math.max(this.maxval, dcr inr - 1); return [inr, dcr]; } }public class Solution { private int maxval 0; public int LongestConsecutive(TreeNode root) { LongestPath(root); return maxval; } private int[] LongestPath(TreeNode root) { if (root null) { return new int[] {0, 0}; } int inr 1, dcr 1; if (root.left ! null) { int[] left LongestPath(root.left); if (root.val root.left.val 1) { dcr left[1] 1; } else if (root.val root.left.val - 1) { inr left[0] 1; } } if (root.right ! null) { int[] right LongestPath(root.right); if (root.val root.right.val 1) { dcr Math.Max(dcr, right[1] 1); } else if (root.val root.right.val - 1) { inr Math.Max(inr, right[0] 1); } } maxval Math.Max(maxval, dcr inr - 1); return new int[] {inr, dcr}; } }func longestConsecutive(root *TreeNode) int { maxval : 0 var longestPath func(root *TreeNode) []int longestPath func(root *TreeNode) []int { if root nil { return []int{0, 0} } inr, dcr : 1, 1 if root.Left ! nil { left : longestPath(root.Left) if root.Val root.Left.Val 1 { dcr left[1] 1 } else if root.Val root.Left.Val - 1 { inr left[0] 1 } } if root.Right ! nil { right : longestPath(root.Right) if root.Val root.Right.Val 1 { if right[1] 1 dcr { dcr right[1] 1 } } else if root.Val root.Right.Val - 1 { if right[0] 1 inr { inr right[0] 1 } } } if dcr inr - 1 maxval { maxval dcr inr - 1 } return []int{inr, dcr} } longestPath(root) return maxval }class Solution { private var maxval 0 fun longestConsecutive(root: TreeNode?): Int { maxval 0 longestPath(root) return maxval } private fun longestPath(root: TreeNode?): IntArray { if (root null) { return intArrayOf(0, 0) } var inr 1 var dcr 1 if (root.left ! null) { val left longestPath(root.left) if (root.val root.left!!.val 1) { dcr left[1] 1 } else if (root.val root.left!!.val - 1) { inr left[0] 1 } } if (root.right ! null) { val right longestPath(root.right) if (root.val root.right!!.val 1) { dcr maxOf(dcr, right[1] 1) } else if (root.val root.right!!.val - 1) { inr maxOf(inr, right[0] 1) } } maxval maxOf(maxval, dcr inr - 1) return intArrayOf(inr, dcr) } }class Solution { private var maxval 0 func longestConsecutive(_ root: TreeNode?) - Int { maxval 0 longestPath(root) return maxval } private func longestPath(_ root: TreeNode?) - [Int] { guard let root root else { return [0, 0] } var inr 1 var dcr 1 if let left root.left { let leftResult longestPath(left) if root.val left.val 1 { dcr leftResult[1] 1 } else if root.val left.val - 1 { inr leftResult[0] 1 } } if let right root.right { let rightResult longestPath(right) if root.val right.val 1 { dcr max(dcr, rightResult[1] 1) } else if root.val right.val - 1 { inr max(inr, rightResult[0] 1) } } maxval max(maxval, dcr inr - 1) return [inr, dcr] } }impl Solution { pub fn longest_consecutive(root: OptionRcRefCellTreeNode) - i32 { let mut maxval 0; Self::longest_path(root, mut maxval); maxval } fn longest_path(root: OptionRcRefCellTreeNode, maxval: mut i32) - (i32, i32) { let node match root { None return (0, 0), Some(n) n.borrow(), }; let mut inr 1; let mut dcr 1; if let Some(ref left) node.left { let (li, ld) Self::longest_path(node.left, maxval); let left_val left.borrow().val; if node.val left_val 1 { dcr ld 1; } else if node.val left_val - 1 { inr li 1; } } if let Some(ref right) node.right { let (ri, rd) Self::longest_path(node.right, maxval); let right_val right.borrow().val; if node.val right_val 1 { dcr dcr.max(rd 1); } else if node.val right_val - 1 { inr inr.max(ri 1); } } *maxval (*maxval).max(dcr inr - 1); (inr, dcr) } }::tabs-end3.5 时间复杂度与空间复杂度时间复杂度$O(n)$空间复杂度$O(n)$其中 $n$ 为输入树的节点数。每个节点恰好被访问一次后序 DFS 的递归深度最坏等于树高退化为链时可达 $O(n)$因此时间与空间均为线性。4. 常见误区排查Common Pitfalls4.1 混淆递增 / 递减的方向归属值为parent.val 1的子节点从「子节点自身视角」看是在延续递增路径但在父节点追踪变量中却被记入dcr因为父节点相对该子节点是递减的。这个命名非常容易搞混。请务必确认每个变量实际追踪的方向# 如果 child.val parent.val - 1父节点扩展的是子节点的递增路径 # 如果 child.val parent.val 1父节点扩展的是子节点的递减路径4.2 合并路径时忘记减 1在节点处拼接递增与递减两条路径时该节点被两边各计数了一次所以公式是inr dcr - 1而不是inr dcr# 错误maxval max(maxval, inr dcr) # 正确maxval max(maxval, dcr inr - 1)这个减 1 是本题最容易被忽视的细节例如某节点自身inr 2节点 → 左子递增、dcr 2节点 → 右子递减真正穿过的节点数是2 2 - 1 3而直接相加会得到错误的 4。4.3 每个方向只考虑一个子节点左右两个子节点都可能对递增或递减路径做出贡献。必须对每个方向都取两个子节点候选长度的最大值而不能假设「左子贡献递增、右子贡献递减」# 错误只取固定一侧 # 正确inr max(inr, left[0] 1, right[0] 1) 的等价写法 # dcr max(dcr, left[1] 1, right[1] 1) 的等价写法对应到代码上就是左子处理时直接赋值、右子处理时与已有值取max见上文各语言实现中左右分支的对称写法。5. 与仓库中相关题解的联系本仓库按语言目录组织题解python/、java/、cpp/、javascript/、csharp/、go/、kotlin/、swift/、rust/等其中已收录与「连续序列」主题相关的姊妹题解数组版最长连续序列题目 128Longest Consecutive Sequence仓库提供了 C 实现、C 实现、Python 实现、Java 实现 等多语言版本其核心是用哈希集合在 $O(n)$ 内寻找连续区间与二叉树版本形成「线性结构 vs 树形结构」的对比可一并阅读加深对连续序列问题的整体理解。二叉树版第 I 题讲解文档 binary-tree-longest-consecutive-sequence.md 详细给出了「自上而下传参」与「自下而上返回长度」两种 DFS并指出第 I 题只允许严格递增方向——与本文第 II 题允许转弯、双向连续形成递进关系推荐按 I → II 的顺序阅读。6. 总结二叉树最长连续序列 II 的核心收获可以浓缩为三点问题升级的本质从「单向递增」变为「递增 / 递减双向且可转弯」要求我们放弃单值状态改为在每个节点维护[inr, dcr]二元状态一次遍历完成后序 DFS 自底向上返回双状态父节点按值差 1 的关系选择性扩展并在每个节点用inr dcr - 1更新全局最大值从而把暴力枚举的 $O(n^3)$ 降到 $O(n)$易错点清单方向归属命名、合并路径减 1、左右子树对两个方向分别取最大值这三处是面试与提交中最常见的失分点。掌握这一「多状态返回值 路径拼接」的套路后还可以顺带迁移到其他树形路径问题如二叉树直径、二叉树最大路径和等中它们共享同一套「在节点处合并左右子树信息」的思维框架。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考