首页/新闻资讯/正文详情

DeepSeek LeetCode 109. 有序链表转换二叉搜索树 Scala实现

发布时间:2026/9/26 11:15:50 来源:云帆数科 栏目:资讯中心
DeepSeek    LeetCode 109. 有序链表转换二叉搜索树 Scala实现
LeetCode 109. 有序链表转换二叉搜索树 — Scala 实现思路转数组 递归构建链表有序BST 中序遍历也有序。最直接的做法把链表值收集到 Array[Int]。递归取中点作为根左右子区间分别构建左右子树自然得到平衡 BST。代码方案一转数组// Definition for singly-linked list.classListNode(var_x:Int0){varnext:ListNodenullvarx:Int_x}// Definition for a binary tree node.classTreeNode(var_value:Int0){varvalue:Int_valuevarleft:TreeNodenullvarright:TreeNodenull}objectSolution{defsortedListToBST(head:ListNode):TreeNode{// 1. 链表转数组valbufscala.collection.mutable.ArrayBuffer.empty[Int]varcurheadwhile(cur!null){bufcur.x curcur.next}valarrbuf.toArray// 2. 递归构建平衡 BSTdefbuild(lo:Int,hi:Int):TreeNode{if(lohi)nullelse{valmid(lohi)1valnodenewTreeNode(arr(mid))node.leftbuild(lo,mid-1)node.rightbuild(mid1,hi)node}}build(0,arr.length-1)}}代码方案二中序遍历模拟空间 O(log n)不额外开数组用可变的链表当前节点指针配合中序递归objectSolution{defsortedListToBST(head:ListNode):TreeNode{// 1. 计算链表长度varn0varpheadwhile(p!null){n1;pp.next}// 用一个可变的当前链表指针模拟中序遍历varcur:ListNodeheaddefbuild(lo:Int,hi:Int):TreeNode{if(lohi)nullelse{valmid(lohi)1// 先构建左子树会消费链表前半部分valleftbuild(lo,mid-1)// 当前链表节点即根valrootnewTreeNode(cur.x)curcur.next root.leftleft// 再构建右子树root.rightbuild(mid1,hi)root}}build(0,n-1)}}复杂度分析方案 时间复杂度 空间复杂度转数组 O(n) O(n)数组中序模拟 O(n) O(log n)递归栈关键点中序模拟的核心先递归左子树此时链表指针 cur 恰好停在当前根位置取完根后指针后移再递归右子树。这样把链表的顺序和BST 的中序顺序对齐无需随机访问。Scala 的 var cur 闭包捕获嵌套函数 build 能直接读写外层 var cur等价于其他语言的 nonlocal / 可变引用写起来比 Rust 简洁很多。1无符号右移取中点避免 (lo hi) 溢出虽然本题范围安全但这是好习惯。推荐方案二空间更优且不依赖额外数组Scala 中可读性也好推荐优先掌握。

相关推荐

PowerShell 网络监控脚本:延迟超阈值自动推送到手机(附防抖与告警去重)
PowerShell 网络监控脚本:延迟超阈值自动推送到手机(附防抖与告警去重)

摘要:不用装任何第三方工具,用 Windows 自带的 PowerShell 写一个网络监控脚本:定时 ping 内网业务地址和隧道外网地址,延迟超阈值或不通时,通过企业微信群机器人 Webhook 或 Server酱推到手机。脚本带三重防骚扰设计 … · 2026/9/26 11:15:44

DeepSeek    LeetCode 109. 有序链表转换二叉搜索树 Python3实现
DeepSeek LeetCode 109. 有序链表转换二叉搜索树 Python3实现

LeetCode 109. 有序链表转换二叉搜索树 — Python3 实现 思路:中序遍历模拟 二叉搜索树(BST)的中序遍历结果是有序的,而给定的链表恰好也是有序的。因此可以模拟中序遍历的过程来构建 BST: 先计算链表的长度 n。递归函… · 2026/9/26 11:15:44

SOM:无监督学习的「聚类之王」,为什么它能「自组织」?
SOM:无监督学习的「聚类之王」,为什么它能「自组织」?

从竞争学习到 Kohonen 网络,理解无监督聚类的数学本质开头:不需要标签也能学习? 上一篇我们学习了 PCA,它是有监督的降维(需要标签来计算方差)。 今天我们学习自组织映射(SOM)——一… · 2026/9/26 11:15:44

紧急修复!OpenClaw 2026.3.13 安全更新,公开部署速配 TaoToken 通道
紧急修复!OpenClaw 2026.3.13 安全更新,公开部署速配 TaoToken 通道

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 12:59:20

VSCode 配置详解:离线版安装插件与 TaoToken 统一 Key 接入
VSCode 配置详解:离线版安装插件与 TaoToken 统一 Key 接入

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 12:59:20

从实战中来:Claude Code 终端 AI 编程代理配置 TaoToken 实战指南
从实战中来:Claude Code 终端 AI 编程代理配置 TaoToken 实战指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 12:59:20

模型量化:GGUF/AWQ/GPTQ部署方案
模型量化:GGUF/AWQ/GPTQ部署方案

模型量化:GGUF/AWQ/GPTQ部署方案 专栏:AI/LLM工程化实战 - 从Prompt到Agent的完整落地指南 模块6 模型微调与部署篇 第61篇 摘要 摘要:模型量化把FP16权重压到INT4,7B模型显存从14GB降到4GB,GGUF、AWQ、GPTQ三种方案各管一块地盘,本文讲透量化… · 2026/9/26 12:59:14

TransactionManager详解:Spring事务失效排查与边界设计实践
TransactionManager详解:Spring事务失效排查与边界设计实践

前天排查一个线上问题,代码里明明白白写着Transactional(rollbackFor Exception.class),库存也扣了,可订单状态偏偏没更新,最后定位到是同一个类内部的this.updateStock()自调用,事务管理器压根没参与。类似的事我这些… · 2026/9/26 12:59:01

AI Agent落地实战指南:从伪智能到真生产力
AI Agent落地实战指南:从伪智能到真生产力

1. 项目概述:这不只是份报告,而是AI Agent落地前的“施工图纸”“36氪研究院 | 2026年中国AI Agent行业发展研究报告”——光看标题,很多人第一反应是“又一份行业白皮书”,随手划走。但如果你正带技术团队做智能客服升级、在规划… · 2026/9/26 12:59:01

数据库课后习题答案别硬背:当测试用例集刷,效率翻倍
数据库课后习题答案别硬背:当测试用例集刷,效率翻倍

简介:万常选版《数据库原理与设计》课后习题答案资源,覆盖第2至6章及第9章,适合正在学习关系模型、数据库建模、关系数据理论与模式求精的本科生、自学者作为复习与自测材料。压缩包共7个文件,含3个doc参考答案、2个sql示例脚本、… · 2026/9/26 0:00:21

OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置
OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 0:00:40

向下兼容与向上兼容:接口设计中的兼容性策略与工程实践
向下兼容与向上兼容:接口设计中的兼容性策略与工程实践

一次版本升级事故,是很多团队绕不过去的坎。线上环境里,服务端明明已经上线了新版接口,老的移动端还在照着旧文档传参数。请求一到网关,校验直接拒绝,用户操作失败,客服群炸了锅,开发群里开始互… · 2026/9/26 0:00:46

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码