LeetCode 109. 有序链表转换二叉搜索树

题目描述
给定一个单链表的头节点 head，其中元素已经按升序排列。请你将其转换为高度平衡的二叉搜索树（BST）。高度平衡二叉树是指一个二叉树的每个节点的左右两个子树的高度差的绝对值不超过 1。

例如：
输入：head = [-10, -3, 0, 5, 9]
输出（可能的一种结果）：

     0
    / \
  -3   9
  /   /
-10  5

解题思路分析

1. 二叉搜索树（BST）的性质：

   • 对于任意节点，左子树的所有节点值小于它，右子树的所有节点值大于它。
   • 如果 BST 的中序遍历是升序序列，那么给定的链表正好就是 BST 的中序遍历结果。

2. 高度平衡的要求：

   • 需要让树的左右子树节点数尽量接近，这样高度差才能最小。
   • 链表的中间节点作为根节点，可以自然平衡左右子树。

3. 关键难点：

   • 链表不能像数组一样随机访问中间元素。
   • 需要一种方法在不重复遍历的情况下找到中间节点并递归构建子树。

解题步骤详解

方法：分治 + 快慢指针找中点

步骤 1：递归框架设计
函数 sortedListToBST(head) 作用：

• 输入：链表当前区间头节点。
• 输出：对应区间的平衡 BST 根节点。

递归过程：

1. 找到当前链表区间的中间节点，作为 BST 根节点。
2. 将链表分为左半部分和右半部分（注意断开中间节点与前一个节点的连接）。
3. 递归构建左子树和右子树。

步骤 2：如何找到链表的中间节点
使用快慢指针法：

• 慢指针 slow 每次走一步，快指针 fast 每次走两步。
• 当 fast 走到末尾时，slow 正好在中间。
• 同时，我们需要记录 slow 的前一个节点 prev，以便断开链表。

示例链表：[-10, -3, 0, 5, 9]

• 初始：slow = head(-10)，fast = head，prev = null
• 第一步：slow = -10，fast = 0
• 第二步：slow = -3，fast = 9
• 第三步：slow = 0，fast = null
  此时 slow = 0 是中间节点，prev = -3。

步骤 3：断开链表并递归

• 根节点 mid = slow（值为 0）。
• 左半部分链表是 head 到 prev（prev.next = null 断开）。
• 右半部分链表是 mid.next 开始。
• 递归构建：
  • 左子树：sortedListToBST(左半部分头)
  • 右子树：sortedListToBST(右半部分头)

步骤 4：递归终止条件
如果当前链表区间为空（head == null），返回 null。

步骤 5：举例模拟过程
链表：[-10, -3, 0, 5, 9]

1. 找中间节点：

   • slow 停在 0，prev = -3，断开 prev.next = null。
   • 根节点 0，左链表 [-10, -3]，右链表 [5, 9]。

2. 递归左链表 [-10, -3]：

   • 找中间：slow = -10，fast = -3（结束时 slow 在 -10，prev = null）
   • 根节点 -10，左链表 null，右链表 [-3]。
   • 递归右链表 [-3]：
     • 中间节点 -3，左右均为 null。
   • 结果左子树：

        -10
          \
           -3
     

3. 递归右链表 [5, 9]：

   • 中间节点 5，左链表 null，右链表 [9]。
   • 递归右链表 [9]：根节点 9，左右均为 null。
   • 结果右子树：

        5
         \
          9
     

4. 组合起来：

       0
      / \
   -10   5
     \    \
     -3    9
   

步骤 6：复杂度分析

• 时间复杂度：O(n log n)。每次找中点需要 O(n/2) 时间，递归深度 O(log n)。
• 空间复杂度：O(log n)，递归栈深度。

代码实现（Java）

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        
        // 快慢指针找中点，同时记录中点前一个节点
        ListNode prev = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 断开链表
        if (prev != null) prev.next = null;
        
        // 中间节点作为根
        TreeNode root = new TreeNode(slow.val);
        // 递归构建左右子树
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        
        return root;
    }
}

总结
本题结合了链表操作与平衡二叉搜索树的构建，核心技巧是快慢指针找链表中点实现分治。通过递归，每次将中间节点作为根，保证了 BST 的有序性和高度平衡性。需要注意链表断开细节，避免形成环或访问错误区间。