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 中可读性也好推荐优先掌握。
