Python solutions (convert to array first, top-down approach, bottom-up approach)


  • 10
    C
    # convert linked list to array
    def sortedListToBST1(self, head):
        ls = []
        while head:
            ls.append(head.val)
            head = head.next
        return self.helper(ls, 0, len(ls)-1)
    
    def helper(self, ls, start, end):
        if start > end:
            return None
        if start == end:
            return TreeNode(ls[start])
        mid = (start+end) >> 1
        root = TreeNode(ls[mid])
        root.left = self.helper(ls, start, mid-1)
        root.right = self.helper(ls, mid+1, end)
        return root
    
    # top-down approach, O(n*logn)
    def sortedListToBST2(self, head):
        if not head:
            return 
        if not head.next:
            return TreeNode(head.val)
        dummy = ListNode(0)
        dummy.next = head
        slow, fast = dummy, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        root = TreeNode(slow.next.val)
        root.right = self.sortedListToBST(slow.next.next)
        slow.next = None
        root.left = self.sortedListToBST(head)
        return root
        
    # bottom-up approach, O(n)
    def sortedListToBST3(self, head):
        l, p = 0, head
        while p:
            l += 1
            p = p.next
        return self.convert([head], 0, l-1)
        
    def convert(self, head, start, end):
        if start > end:
            return None
        mid = (start + end) >> 1
        l = self.convert(head, start, mid-1)
        root = TreeNode(head[0].val)
        root.left = l
        head[0] = head[0].next 
        root.right = self.convert(head, mid+1, end)
        return root
    
    # bottom-up approach, O(n)    
    def sortedListToBST(self, head):
        l, p = 0, head
        while p:
            l += 1
            p = p.next
        self.node = head
        return self.convert(0, l-1)
        
    def convert(self, start, end):
        if start > end:
            return None
        mid = (start + end) >> 1
        l = self.convert(start, mid-1)
        root = TreeNode(self.node.val)
        root.left = l
        self.node = self.node.next 
        root.right = self.convert(mid+1, end)
        return root

  • 0
    Z

    Thanks for sharing! Could you please explain more details about the first bottom-up approach? I can't get the recursion process. Thanks!!


  • 0
    C

    Yes, the bottom-up one is not easy to think out, I also refered others' work. The main idea is as the list is sorted, the first element should be placed on the bottom-left of the final BST, then the second element should be placed on the root position of the first element, and continue do like this.


  • 0
    D
    class Solution(object):
        def sortedListToBST(self, head):
            """
            :type head: ListNode
            :rtype: TreeNode
            """
            if head == None:
                return None
    
            l = [head.val]
    
            while head.next is not None:
                head = head.next
                l.append(head.val)
    
            def toTreeNode(lst):
                if len(lst) == 0:
                    return None
    
                m = len(lst) / 2
                l = m - 1
                r = m + 1
                n = TreeNode(lst[m])
    
                if l >= 0:
                    n.left = toTreeNode(lst[0:l+1])
    
                if r < len(lst):
                    n.right = toTreeNode(lst[r:len(lst)])
    
                return n
    
            return toTreeNode(l)

  • 0
    F

    Hi caikehe, thanks for sharing your solution. Can you tell me why you need to write [head] instead of just head in the helper function? I'm kinda confused in some aspects of the linked list.


  • 0
    Y

    @fungyh Good question. I'll try to explain since it will hopefully help my own understanding ;).

    Using a list allows the function call that creates the left subtree to update node[0] with the next list node that needs to be converted into a tree node. Passing a list node directly without the list wrapper would mean the root would be the first (i.e smallest value) of the list, which is not what we want. We want to use all the smaller values in the left subtree first before using the mid value for the root.

    I guess node could equally well be a set containing a single item of head. Any mutable structure will do.
    The other version below called "sortedListToBST" achieves the same effect by declaring a class attribute self.node that can also be updated by other function calls.
    Both of which are similar to using a global variable.

    I'm not sure what is most pythonic. Using a list purely to contain a variable seems to be slightly cheating. But then class attributes should ideally be declared in an init method?


  • 0
    T

    That bottom-up approach is very clever. Thank you for sharing that.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.