题目

题解

分治。

class Solution:

    def getMedian(self, left: ListNode, right: ListNode) -> ListNode:
            '''找到链表的中间节点'''
            slow = fast = left
            while fast != right and fast.next != right:
                slow = slow.next
                fast = fast.next.next
            return slow

    def buildTree(self, left: ListNode, right: ListNode) -> TreeNode:
        """左闭右开"""
        if left == right:
            return None
        mid = self.getMedian(left, right)
        root = TreeNode(mid.val)
        root.left = self.buildTree(left, mid)
        root.right = self.buildTree(mid.next, right)
        return root

    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        return self.buildTree(head, None)