LC109. 有序链表转换平衡二叉搜索树

LC109. 有序链表转换平衡二叉搜索树

题目要求

(一)快慢指针

要将一个按升序排列的单链表转换为平衡的二叉搜索树（BST），可以采用以下步骤：

1. 理解问题

• 单链表：链表中的节点按升序排列。
• 平衡二叉搜索树：树的左右子树高度差不超过1，且左子树的值小于根节点，右子树的值大于根节点。

2. 解决思路

由于链表是升序排列的，我们可以将其视为二叉搜索树的中序遍历结果。为了构建平衡的BST，我们需要找到链表的中间节点作为根节点，然后递归地构建左子树和右子树。

3. 具体步骤

1. 找到链表的中间节点：

   • 使用快慢指针法找到链表的中间节点。快指针每次走两步，慢指针每次走一步，当快指针到达链表末尾时，慢指针指向的就是中间节点。

2. 递归构建BST：

   • 将中间节点作为根节点。
   • 递归地构建左子树（链表的前半部分）和右子树（链表的后半部分）。

3. 处理边界条件：

   • 如果链表为空，返回 null。
   • 如果链表只有一个节点，直接返回该节点作为树的根节点。

4. 代码实现

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef sortedListToBST(head):if not head:return None# 找到链表的中间节点def findMiddle(head):slow = headfast = headprev = Nonewhile fast and fast.next:prev = slowslow = slow.nextfast = fast.next.next# 断开链表if prev:prev.next = Nonereturn slow# 递归构建BSTdef buildBST(head):if not head:return Nonemid = findMiddle(head)root = TreeNode(mid.val)# 如果只有一个节点，直接返回if head == mid:return root# 递归构建左子树和右子树root.left = buildBST(head)root.right = buildBST(mid.next)return rootreturn buildBST(head)

5. 复杂度分析

• 时间复杂度：O(N log N)，其中 N 是链表的长度。每次递归都需要找到中间节点，时间复杂度为 O(N)，递归深度为 O(log N)。
• 空间复杂度：O(log N)，递归栈的深度为 O(log N)。

6. 示例解释

对于输入 head = [-10,-3,0,5,9]：

• 中间节点是 0，作为根节点。
• 左子树由 [-10, -3] 构建，右子树由 [5, 9] 构建。
• 最终得到的平衡BST为 [0,-3,9,-10,null,5]。

7. 总结

通过找到链表的中间节点并将其作为根节点，然后递归地构建左子树和右子树，我们可以将一个升序链表转换为一个平衡的二叉搜索树。这种方法既保证了树的平衡性，又充分利用了链表的升序特性。