微信开发 微网站开发的详细流程,做交通事故的网站,wordpress 我爱搜罗网,网页制作的工作岗位文章目录 摘要描述举个例子#xff1a; 题解答案题解代码分析#xff08;Swift#xff09;示例测试及结果输出结果#xff1a; 时间复杂度分析空间复杂度分析总结 摘要
这篇文章会带你用 Swift 编写一个算法#xff0c;找出一棵二叉树中最长的「连续递增路径」。不是数组… 文章目录 摘要描述举个例子 题解答案题解代码分析Swift示例测试及结果输出结果 时间复杂度分析空间复杂度分析总结 摘要
这篇文章会带你用 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”这个判断逻辑整套算法就水到渠成了。
这类题在实际开发中挺有意思比如
判断某些数据是否形成稳定增长序列日志中查找连续变化事件游戏场景里记录连续操作行为
