Leetcode 109.有序链表转换二叉搜索树

109.有序链表转换二叉搜索树

题目

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

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

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

方法

方法1：快慢指针$\text {时间复杂度：} O(N \log N) \text {空间复杂度：} O(\log N)$

给定有序链表的中间元素构建二叉搜索树的根节点。链表中在中间元素左侧的元素递归地构建左子树，在中间元素右侧的元素构建右子树。这可以保证最终的二叉搜索树的高度平衡。

给定链表，不能采用索引获取链表的元素，但需要知道链表中的中间元素
采用双指针方法找出中间元素，称为快慢指针。当慢指针slow_ptr移动一个结点，快指针fast_ptr移动两个结点。当快指针fast_ptr到达链表最后一个结点，慢指针slow_ptr就到达中间元素了。如果链表长度是偶数，那两个中间元素的任意一个都可作为二叉搜索树的中间元素。
一旦获得链表的中间元素，需要断开其左侧元素。采用pre_ptr记录漫之阵的前一个指针pre_ptr.next=slow_ptr。当要断开这两者之间的联系，直接pre_ptr.next=None
我们只需要传递链表的头指针到函数中，将其转换为高度平衡的二叉搜索树。所以，递归地调用链表的左半部分（链表的头指针）和链表的右半部分（slow_ptr.next作为头指针）

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        # 如果head不存在，链表是空的
        if not head:
            return

        # 找到链表的中间元素
        mid=self.findMiddle(head)

        # 中间元素作为二叉搜索树的根结点
        node=TreeNode(mid.val)

        # 基本情况：当链表中只有一个元素
        if head==mid:
            return node

        # 采用链表的左半部分和右半部分，递归构建二叉搜索树
        node.left=self.sortedListToBST(head)
        node.right=self.sortedListToBST(mid.next)
        return node


    def findMiddle(self,head):
        pre=None
        slow=head
        fast=head

        while fast and fast.next:
            pre=slow
            slow=slow.next
            fast=fast.next.next
        if pre:
            pre.next=None
        return slow

Leetcode Solution:时间和空间复杂度

方法2：递归+转换为数组 $\text {时间复杂度：} O(N) \text {空间复杂度：} O(N)$

将链表转换为数组，采用数组构建二叉搜索树。在数组中获取中间元素是O(1)，这可以降低时间复杂度。

将链表转换为数组，数组两端分别称为left\right
找到中间元素(left+right)/2，记作mid。时间是O(1)
中间元素作为二叉搜索树的根结点
递归地从数组的两半部分(left,mid-1)、(mid+1,right)构建二叉搜索树

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        array=self.mapListToArray(head)

        def convertListToBST(l,r):
            if l>r:
                return None
            mid=(l+r)/2
            node=TreeNode(array[mid])

            if l==r:
                return node

            node.left=convertListToBST(l,mid-1)
            node.right=convertListToBST(mid+1,r)
            return node
        return convertListToBST(0,len(array)-1)

    def mapListToArray(self,head):
        array=[]
        while head:
            array.append(head.val)
            head=head.next
        return array

Leetcode Solution:时间和空间复杂度