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

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

思路：转数组 + 递归构建

链表有序，BST 中序遍历也有序。最直接的做法：

1. 把链表值收集到 Array[Int]。
2. 递归取中点作为根，左右子区间分别构建左右子树，自然得到平衡 BST。

代码（方案一：转数组）

// Definition for singly-linked list.classListNode(var_x:Int=0){varnext:ListNode=nullvarx:Int=_x}// Definition for a binary tree node.classTreeNode(var_value:Int=0){varvalue:Int=_valuevarleft:TreeNode=nullvarright:TreeNode=null}objectSolution{defsortedListToBST(head:ListNode):TreeNode={// 1. 链表转数组valbuf=scala.collection.mutable.ArrayBuffer.empty[Int]varcur=headwhile(cur!=null){buf+=cur.x cur=cur.next}valarr=buf.toArray// 2. 递归构建平衡 BSTdefbuild(lo:Int,hi:Int):TreeNode={if(lo>hi)nullelse{valmid=(lo+hi)>>>1valnode=newTreeNode(arr(mid))node.left=build(lo,mid-1)node.right=build(mid+1,hi)node}}build(0,arr.length-1)}}

代码（方案二：中序遍历模拟，空间 O(log n)）

不额外开数组，用可变的"链表当前节点"指针配合中序递归：

objectSolution{defsortedListToBST(head:ListNode):TreeNode={// 1. 计算链表长度varn=0varp=headwhile(p!=null){n+=1;p=p.next}// 用一个可变的当前链表指针模拟中序遍历varcur:ListNode=headdefbuild(lo:Int,hi:Int):TreeNode={if(lo>hi)nullelse{valmid=(lo+hi)>>>1// 先构建左子树（会消费链表前半部分）valleft=build(lo,mid-1)// 当前链表节点即根valroot=newTreeNode(cur.x)cur=cur.next root.left=left// 再构建右子树root.right=build(mid+1,hi)root}}build(0,n-1)}}

复杂度分析

方案 时间复杂度 空间复杂度
转数组 O(n) O(n)（数组）
中序模拟 O(n) O(log n)（递归栈）

关键点

1. 中序模拟的核心：先递归左子树，此时链表指针 cur 恰好停在"当前根位置"，取完根后指针后移，再递归右子树。这样把"链表的顺序"和"BST 的中序顺序"对齐，无需随机访问。
2. Scala 的 var cur 闭包捕获：嵌套函数 build 能直接读写外层 var cur，等价于其他语言的 nonlocal / 可变引用，写起来比 Rust 简洁很多。

3. 1：无符号右移取中点，避免 (lo + hi) 溢出（虽然本题范围安全，但这是好习惯）。

4. 推荐：方案二空间更优且不依赖额外数组，Scala 中可读性也好，推荐优先掌握。