知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 05 - 有序链表转换为二叉搜索树 ## 题目(LeetCode 109) 给定一个升序排列的单链表,将其转换为高度平衡的二叉搜索树。 ``` 输入:head = [-10,-3,0,5,9] 输出:[0,-3,9,-10,null,5] ``` ## 核心思路 和 108 题(有序数组转 BST)思路一样:取中间元素做根。区别是链表不能 O(1) 随机访问,需要用快慢指针找中点。 ``` 链表:-10 → -3 → 0 → 5 → 9 快慢指针找中点: slow = -10, fast = -10 slow = -3, fast = 0 slow = 0, fast = 9(fast.next.next == null,停止) → 中点 = 0 0 做根,左半链表 [-10, -3],右半链表 [5, 9] 递归构造 ``` ## 代码 ```java class Solution { public TreeNode sortedListToBST(ListNode head) { if (head == null) return null; if (head.next == null) return new TreeNode(head.val); // 快慢指针找中点,prev 记录中点前一个节点用于断链 ListNode prev = null, slow = head, fast = head; while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } // slow 就是中点,prev 用于断开左半链表 if (prev != null) prev.next = null; TreeNode root = new TreeNode(slow.val); root.left = sortedListToBST(head == slow ? null : head); // 左半 root.right = sortedListToBST(slow.next); // 右半 return root; } } ``` ## 解法二:中序遍历模拟(更优雅) 利用 BST 的中序遍历就是有序序列这个性质,边遍历链表边构造树: ```java class Solution { private ListNode cur; public TreeNode sortedListToBST(ListNode head) { // 先算链表长度 int size = 0; for (ListNode p = head; p != null; p = p.next) size++; cur = head; return build(0, size - 1); } private TreeNode build(int lo, int hi) { if (lo > hi) return null; int mid = lo + (hi - lo) / 2; // 先构造左子树(中序:左→根→右) TreeNode left = build(lo, mid - 1); // 当前链表节点就是根 TreeNode root = new TreeNode(cur.val); cur = cur.next; // 链表指针前进 root.left = left; root.right = build(mid + 1, hi); return root; } } ``` ### 为什么这个方法可行? ``` BST 的中序遍历 = 有序序列 = 链表顺序 构造过程模拟中序遍历: 先递归构造左子树 → 此时链表指针刚好走到中间节点 → 取当前节点做根 → 指针前进 → 递归构造右子树 链表指针和递归过程完美同步,不需要找中点! ``` ## 两种解法对比 | | 解法一(快慢指针) | 解法二(中序模拟) | |--|--------|--------| | 时间复杂度 | O(n log n)(每层找中点 O(n)) | O(n) | | 空间复杂度 | O(log n) | O(log n) | | 特点 | 直观,和数组版思路一致 | 更优,利用中序遍历性质 | ## 复杂度 - 解法一:时间 O(n log n),空间 O(log n) - 解法二:时间 O(n),空间 O(log n) --- 上一篇:[04 - 将有序数组转换为 BST](./04-sorted-array-to-bst.md) | 下一篇:[06 - 前序遍历构造 BST](./06-bst-from-preorder.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入