Leetcode 109：有序链表转换二叉搜索树（超详细的解法！！！）

小编 2026-06-09 阅读:308 评论:0

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。示例: 给定的有序链表：...

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \\
   -3   9
   /   /
 -10  5

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

解题思路

我们知道二分搜索数的中序遍历就是一个单调递增的序列，那么这个问题其实就是中序遍历转化为二分搜索树。和此类似的问题有

Leetcode 105：从前序与中序遍历序列构造二叉树（最详细的解法！！！）

Leetcode 106：从中序与后序遍历序列构造二叉树（最详细的解法！！！）

一个非常容易想到的思路就是递归，我们可以将中间的元素mid放在root，然后将[:mid-1]放在root.left，在[mid+1:]放在root.right。但是题设给我们的是一个链表，所以我们我们无法快速求解出mid的位置，我们可以现将链表转化成数组就可以啦。

class Solution:
    def sortedListToBST(self, head):
        \"\"\"
        :type head: ListNode
        :rtype: TreeNode
        \"\"\"
        list_bst = list()
        while head:
            list_bst.append(head.val)
            head = head.next
            
        return self.convertBST(0, len(list_bst) - 1, list_bst)
         
    def convertBST(self, left, right, list_bst):
        if left > right:
            return
        
        mid = (left + right)//2
        res = TreeNode(list_bst[mid])
        res.left = self.convertBST(left, mid - 1, list_bst)
        res.right = self.convertBST(mid + 1, right, list_bst)
        return res

对于这种中点问题一个常见的处理思路就是通过快慢指针。我们可以建立两个指针slow和fast，其中一个slow=slow.next，另外一个fast=fast.next.next，这样当我们的fast指向最后节点的时候，slow一定是指向中间节点的。但是此时有一个问题

我们此时无法知道slow的前一个位置了。怎么办？我们可以让fast提前跑。具体操作如下

class Solution:
    def sortedListToBST(self, head):
        \"\"\"
        :type head: ListNode
        :rtype: TreeNode
        \"\"\"
        if not head:
            return 
        
        if not head.next:
            return TreeNode(head.val)
        
        slow, fast = head, head.next.next # fast
        while fast and fast.next:
            slow = slow.next 
            fast = fast.next.next
            
        tmp = slow.next
        slow.next = None
        res = TreeNode(tmp.val)
        res.left = self.sortedListToBST(head)
        res.right = self.sortedListToBST(tmp.next)
        return res

fast提前跑后，slow.next就变成了mid的位置。非常好的思路。

对于这个问题，我们可以从后向前思考，我们可以先找到左下角的树，然后再往上递推。

class Solution:
    def sortedListToBST(self, head):
        \"\"\"
        :type head: ListNode
        :rtype: TreeNode
        \"\"\"
        cur = head
        list_len = 0
        while cur:
            cur = cur.next
            list_len += 1
            
        self.node = head
        return self.convertBST(0, list_len - 1)
        
    def convertBST(self, left, right):
        if left > right:
            return
        
        mid = (left + right)//2
        left = self.convertBST(left, mid - 1)
        res = TreeNode(self.node.val)
        res.left = left
        
        self.node = self.node.next
        
        right = self.convertBST(mid + 1, right)
        res.right = right
        return res