这个题解的思路是使用快慢指针找到链表的中点,然后递归地将左右两个子链表转换为左右子树。具体步骤如下:
1. 如果链表为空,直接返回None;如果链表只有一个节点,则直接返回这个节点为根的树。
2. 使用快慢指针找到链表的中点,慢指针每次走一步,快指针每次走两步,当快指针走到末尾时,慢指针指向中点。
3. 将中点的值作为根节点的值,然后递归地将中点左边的链表转换为左子树,中点右边的链表转换为右子树。
4. 返回根节点。
时间复杂度: O(nlogn)
空间复杂度: O(n)
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if head is None:
return None
if head.next is None:
return TreeNode(head.val)
# 使用快慢指针找到链表的中点
f = head
s = head
pre = None
while f and f.next:
f = f.next.next
pre = s
s = s.next
# 将中点左边的链表断开
pre.next = None
right = s.next
# 创建根节点,递归构建左右子树
root = TreeNode(s.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(right)
return root