Short python solution based on Sorted Array


  • 0
    C

    Based on 108. Convert Sorted Array to Binary Search Tree. Basically just convert the sorted linked list head into a sorted array nums and then build the tree. It's O(n) in space but it's concise and fast. Runtime is ~260ms on OJ.

    def sortedListToBST(self, head):
        def helper(L, R):
            if L <= R:
                mid = L+(R-L+1)/2
                root = TreeNode(nums[mid])
                root.left = helper(L, mid-1)
                root.right = helper(mid+1, R)
                return root
        nums, node = [], head
        while node:
            nums.append(node.val)
            node = node.next
        return helper(0, len(nums)-1)

Log in to reply
 

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