有序链表转换二叉搜索树

标签: 二叉搜索树 链表 分治 二叉树

难度: Medium

给定一个单链表的头节点  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 * 104] 范围内
  • -105 <= Node.val <= 105

Submission

运行时间: 80 ms

内存: 17.9 MB

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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

Explain

这个题解的思路是使用快慢指针找到链表的中点,然后递归地将左右两个子链表转换为左右子树。具体步骤如下: 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

Explore

在使用快慢指针策略时,慢指针(s)始终指向中点或中点附近的节点,而快指针(f)以两倍速度移动。当快指针到达链表末尾时,慢指针就位于中间位置。对于偶数节点的链表,此方法将导致慢指针停留在中间两个节点的第一个。通过在慢指针前维护一个指针(pre),我们可以在找到中点后将链表从中点前一个节点断开,从而将链表分为两部分。这样,即使是偶数个节点,链表也总是被分割成两个几乎等长的部分,左边包含中点前的所有节点,右边包含中点后的所有节点。

`pre` 变量的作用是跟踪慢指针(s)的前一个节点。这是必要的,因为一旦找到中点,我们需要将链表从中点前一个节点断开,以便递归构造左子树。如果没有`pre`,我们无法断开链表。快指针(f)以两倍的速度移动,而慢指针(s)以一倍速度移动,因此当快指针达到链表末尾时,慢指针恰好达到整个链表的中间位置。在偶数节点的情况下,这种方法使慢指针指向中间两个节点的第一个,而在奇数节点的情况下,慢指针正好指向中点。

当链表为空时,没有节点可以转换为二叉搜索树,因此返回`None`是合理的,表示树为空。当链表只有一个节点时,这个节点本身就可以直接成为二叉搜索树的根节点,因为没有其他节点与之比较,它自然满足二叉搜索树的要求(即根节点大于左子树中的所有节点且小于右子树中的所有节点)。这种处理逻辑简化了递归调用,因为它处理了递归的基本情况,避免了进一步的递归,从而提高了效率并简化了代码。