题目

题解

分治。

class Solution:def getMedian(self, left: ListNode, right: ListNode) -> ListNode:'''找到链表的中间节点'''slow = fast = leftwhile fast != right and fast.next != right:slow = slow.nextfast = fast.next.nextreturn slowdef buildTree(self, left: ListNode, right: ListNode) -> TreeNode:"""左闭右开"""if left == right:return Nonemid = self.getMedian(left, right)root = TreeNode(mid.val)root.left = self.buildTree(left, mid)root.right = self.buildTree(mid.next, right)return rootdef sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:return self.buildTree(head, None)