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

https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/

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

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

示例:

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

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

通过次数32,451 | 提交次数44,597

Second Try

2020-07-09

升序排列本身就是二叉搜索树的中序排列，每次找到中间点分为left right就可以了。

至于在链表里找中点，以前只会遍历，而且需要1.5遍；现在还知道有快慢指针方法，虽然其实也是遍历了一遍，但一遍就能确定了。

就因为这道题，专门去把二叉树前序中序后序排列都做了一遍，又花去了许多时间，蜗牛般的速度。

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        # 升序排列本身就是中序排列，每次找到中间点分为left right就可以了
        if not head:
            return None 
        if not head.next:
            return TreeNode(head.val)
        fast = head.next
        slow = head
        dummy = ListNode(None)
        dummy.next = head 
        preslow = dummy 
        while fast.next:
            preslow = slow 
            slow = slow.next
            if fast.next.next:
                fast = fast.next.next
            else:
                fast = fast.next 

        root = TreeNode(slow.val)
        root.right = self.sortedListToBST(slow.next)
        preslow.next = None 
        root.left = self.sortedListToBST(dummy.next)
        return root 

执行用时：68 ms, 在所有 Python 提交中击败了50.51%的用户
内存消耗：20.1 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-07-06

将链表转化为列表，然后再将列表通过递归转化为高度平衡二叉树，不知道算不算作弊。纯用链表真是想不出来，要么复杂度爆炸。

# 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
        """
        # 把链表转化为列表算不算作弊？
        if not head:
            return None

        arr = [head]
        while arr[-1].next:
            arr.append(arr[-1].next)

        def buildTree(arr, left, right):
            if left > right:
                return None
            mid = (left + right) / 2
            root = TreeNode(arr[mid].val)
            root.left = buildTree(arr,left, mid - 1)
            root.right = buildTree(arr, mid + 1, right)
            return root 
        
        left, right = 0, len(arr) - 1
        root = buildTree(arr, left, right)
        return root 
        

执行用时：64 ms, 在所有 Python 提交中击败了66.11%的用户
内存消耗：25.7 MB, 在所有 Python 提交中击败了100.00%的用户

109. 有序链表转换二叉搜索树 [medium]​

Second Try​

First Try​

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

Second Try

First Try