Simple python solution with constant space


  • 2
    Y
    class Solution:
    # @param {ListNode} head
    # @return {TreeNode}
    def sortedListToBST(self, head):
        if not head:
            return None
    
        l = 0
        copy = head
        while copy:
            copy = copy.next 
            l += 1
        return self.linkedlist_to_bst_help(0, l, [head])
    
    def linkedlist_to_bst_help(self, start, end, curr):
        if start == end:
            return None
        if start == end - 1:
            node = TreeNode(curr[0].val)
            curr[0] = curr[0].next
            return node
    
        mid = (start + end) / 2
        left = self.linkedlist_to_bst_help(start, mid, curr)
    
        node = TreeNode(curr[0].val)
        curr[0] = curr[0].next
    
        right = self.linkedlist_to_bst_help(mid + 1, end, curr)
    
        node.left = left
        node.right = right
        return node

Log in to reply
 

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