LeetCode 109. 有序链表转换二叉搜索树 — Rust 实现思路转数组 递归构建由于链表有序且二叉搜索树BST的中序遍历结果也是有序的最直接的做法是将链表所有值存入一个 Vec。在有序数组上递归每次取中间元素作为根节点左右子数组分别构建左右子树。这样自然得到一棵高度平衡的 BST。代码usestd::rc::Rc;usestd::cell::RefCell;// Definition for singly-linked list.#[derive(PartialEq, Eq, Clone, Debug)]pubstructListNode{pubval:i32,pubnext:OptionBoxListNode,}implListNode{#[inline]fnnew(val:i32)-Self{ListNode{next:None,val}}}// Definition for a binary tree node.#[derive(Debug, PartialEq, Eq)]pubstructTreeNode{pubval:i32,publeft:OptionRcRefCellTreeNode,pubright:OptionRcRefCellTreeNode,}implTreeNode{#[inline]pubfnnew(val:i32)-Self{TreeNode{val,left:None,right:None,}}}implSolution{pubfnsorted_list_to_bst(head:OptionBoxListNode)-OptionRcRefCellTreeNode{// 1. 链表转数组letmutvalsVec::new();letmutcurhead.as_ref();whileletSome(node)cur{vals.push(node.val);curnode.next.as_ref();}// 2. 递归构建平衡 BSTfnbuild(vals:[i32])-OptionRcRefCellTreeNode{ifvals.is_empty(){returnNone;}letmidvals.len()/2;letnodeRc::new(RefCell::new(TreeNode::new(vals[mid])));node.borrow_mut().leftbuild(vals[..mid]);node.borrow_mut().rightbuild(vals[mid1..]);Some(node)}build(vals)}}复杂度分析· 时间复杂度O(n)链表遍历一次递归构建每个节点访问一次。· 空间复杂度O(n)数组 vals 占用 O(n)递归栈深度 O(log n)总体 O(n)。进阶中序遍历模拟空间 O(log n)如果不想使用额外数组可以模拟中序遍历的过程。在 Rust 中由于所有权和借用检查需要借助 RcRefCell 或 unsafe 来维护当前节点的可变指针实现较为繁琐。核心思路先计算链表长度 n。递归函数 build(start, end)先构建左子树然后取当前链表节点作为根指针后移再构建右子树。需要维护一个可变的链表当前节点引用。由于 Rust 对可变引用的严格限制这种写法通常需要 RefCell 或 Box::leak 等手段代码可读性不如转数组方案。在面试或实际工程中转数组方案简洁且足够高效推荐使用。
