Lazy solution, O(n log n)


  • 0
    N

    Lazy because it's simply reusing code from the previous problem in the series (Convert sorted array). Only thing new to is extract the list node values into an array.

    def list_to_arr(list)
      arr = []
      curr = list
    
      while (curr != nil)
        arr.push(curr.val)
        curr = curr.next
      end
    
      arr
    end
    
    def sorted_array_to_bst(nums)
      len = nums.length
      return nil if len == 0
      return TreeNode.new(nums[0]) if len == 1
    
      ind = len / 2
      root = TreeNode.new(nums[ind])
    
      root.left = sorted_array_to_bst(nums[0..ind - 1]) # exclude `ind`
      root.right = sorted_array_to_bst(nums[ind + 1, len - ind - 1]) # exclude `ind`
    
      root
    end
    
    def sorted_list_to_bst(head)
      arr = list_to_arr(head)
      sorted_array_to_bst(arr)
    end
    
    

Log in to reply
 

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