题目

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

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

示例: 给定的有序链表： [-10, -3, 0, 5, 9], 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5

解题思路

这道题和将有序数组转换为二叉搜索树很相似，就是列表换成了链表。 所以无脑版的思路就是，遍历一次链表，把数值保存在列表里，再左右递归。 更好的思路是，其实我们发现，每次我们重点在于需要找到中间的那个节点，所以如果能找到链表中间的节点，就不用保存到列表里了，这道题就变成了先找链表中间节点，链表从中间断开，再左右递归喽。

时间复杂度$o(n)$

代码

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode: # find middle node if not head: return None if not head.next: return TreeNode(head.val) slow, fast = head, head pre_slow = slow while fast and fast.next: pre_slow = slow slow = slow.next fast = fast.next.next pre_slow.next = None # break link list root = TreeNode(slow.val) root.left = self.sortedListToBST(head) root.right = self.sortedListToBST(slow.next) return root