109. Convert Sorted List to Binary Search Tree

Loading...LeetCode

把Q108改成了在linked list上操作，此时长度无法直接获得，就不能定位中点。

108. Convert Sorted Array to Binary Search Tree

1. 比较暴力的解法是把linked list转换成array，然后复制Q108的操作。

2. 还可以利用BST的性质，先遍历获得linked list的长度，然后in-order去生成BST。但其实这个方法跟前一个相比并无显著优势，同样有临时的额外空间使用，同样需要遍历一次链表。

3. 利用快慢双指针，可以在不获取长度的前提下获得链表的中点，但在时间复杂度上有比较大的牺牲，好处是完全没有使用额外空间。

convert to array

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
            
        def helper(left, right):
            if left <= right: 
                mid = (left + right)//2  # 取左中点
                root = TreeNode(val = nums[mid])
                root.left = helper(left, mid-1)
                root.right = helper(mid+1, right)
                return root
        
        return helper(0, len(nums)-1)

bottom-up grow

class Solution:
    def __init__(self):
        self.valPointer = None
            
    def grow(self, left, right):
        if right >= left:
            mid = (left + right) // 2
            getLeft = self.grow(left, mid-1)
            root = TreeNode(self.valPointer.val)
            root.left = getLeft
            self.valPointer = self.valPointer.next
            root.right = self.grow(mid+1, right)
            return root
        
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        length = 0
        counter = head
        self.valPointer = head
        while counter:
            length += 1
            counter = counter.next
        return self.grow(0, length-1)

two pointer

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head: return None
        if not head.next: return TreeNode(head.val)
        
        root = TreeNode()
        slow, fast = head, head.next.next 
        while fast and fast.next: 
            slow = slow.next
            fast = fast.next.next
        node = slow.next # right half
        slow.next = None # break up the linked list
        
        root.val = node.val
        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(node.next)
        
        return root