目录

0109:有序链表转换二叉搜索树(★)

力扣第 109 题

题目

给定一个单链表的头节点 head ,其中的元素 按升序排序 ,将其转换为 平衡 二叉搜索树。

示例 1:

输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0,-3,9,-10,null,5],它表示所示的高度平衡的二叉搜索树。

示例 2:

输入: head = []
输出: []

提示:

  • head 中的节点数在[0, 2 * 104] 范围内
  • -105 <= Node.val <= 105

相似问题:

分析

0108 升级版,可以用快慢指针在链表上找中点,实现递归。更简单的做法是直接将链表转为数组。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        A = []
        while head:
            A.append(head.val)
            head = head.next
        def dfs(i,j):
            if i>j:
                return None
            k = (i+j)//2
            return TreeNode(A[k],dfs(i,k-1),dfs(k+1,j))
        return dfs(0,len(A)-1)

49 ms