网站制作吧semi认证

摘要

这篇文章会带你用 Swift 编写一个算法，找出一棵二叉树中最长的「连续递增路径」。不是数组那种连续，而是沿着父节点到子节点，只要数值刚好加一，就算连续。我们不仅会实现解法，还会讲清楚怎么递归、怎么处理状态和边界问题。附带 Demo，写完就能跑！

描述

题目大致意思是这样的：

给你一棵二叉树，让你找出最长的一条路径，这条路径需要满足每个节点的值比前一个节点的值正好大 1（比如 1→2→3）。路径必须是从父节点一路走到子节点的，不能反着走，也不能绕道。

举个例子：

    1\3/ \2   4\5

在这棵树里，最长的连续路径是 3→4→5，所以结果是 3。

题解答案

这个题我们可以用递归来做，从每个节点出发，去判断它的左右子树是不是能延续这个连续性。如果能，我们就更新当前的计数。如果不能，就从当前节点重新计数。

我们可以用一个全局变量 maxLength 来存储当前找到的最大连续路径长度。

题解代码分析（Swift）

class TreeNode {var val: Intvar left: TreeNode?var right: TreeNode?init(_ val: Int) {self.val = valself.left = nilself.right = nil}
}class Solution {private var maxLength = 0func longestConsecutive(_ root: TreeNode?) -> Int {guard let root = root else { return 0 }dfs(root, nil, 0)return maxLength}private func dfs(_ node: TreeNode?, _ parent: TreeNode?, _ length: Int) {guard let node = node else { return }let currLength = (parent != nil && node.val == parent!.val + 1) ? length + 1 : 1maxLength = max(maxLength, currLength)dfs(node.left, node, currLength)dfs(node.right, node, currLength)}
}

示例测试及结果

我们来写一个 Demo，跑起来试试看。

func buildTree() -> TreeNode {let root = TreeNode(1)root.right = TreeNode(3)root.right?.left = TreeNode(2)root.right?.right = TreeNode(4)root.right?.right?.right = TreeNode(5)return root
}let root = buildTree()
let solution = Solution()
let result = solution.longestConsecutive(root)
print("最长连续序列长度是：\(result)")  // 输出：3

输出结果：

最长连续序列长度是：3

这个结果就是从 3→4→5 这段路径来的，正好是连续递增，长度是 3。

时间复杂度分析

• 每个节点只会被访问一次，所以整体是 O(n)，其中 n 是节点的总数。
• 在每次递归里我们只是简单做了加法、判断大小这些操作，没有多余的遍历。

空间复杂度分析

• 除了递归调用栈外，我们只用了一个变量 maxLength。
• 所以空间复杂度是 O(h)，h 是树的高度，最坏情况是 O(n)。

总结

这个题目其实是考你怎么在递归中「记住上一层的状态」，再在下一层做对比。只要你理解了“当前值是否比上一个值大 1”这个判断逻辑，整套算法就水到渠成了。

这类题在实际开发中挺有意思，比如：

• 判断某些数据是否形成稳定增长序列
• 日志中查找连续变化事件
• 游戏场景里记录连续操作行为