0109：有序链表转换二叉搜索树（★）

2015-04-19 约 276 字预计阅读 1 分钟次阅读

力扣第 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 * 10⁴] 范围内
-10⁵ <= Node.val <= 10⁵

相似问题：

分析

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

目录

0109：有序链表转换二叉搜索树（★）

题目

分析

解答