BinarySearch 0250 Linked List to Binary Search Tree

Problem statement

https://binarysearch.com/problems/Linked-List-to-Binary-Search-Tree/

Solution

Equal to Leetcode 0109. Convert Sorted List to Binary Search Tree

Complexity

Time and space is O(n).

Code

class Solution:
    def solve(self, head):
        def helper(beg, end):
            if beg > end: return None
            mid = (beg + end + 1)//2
            left = helper(beg, mid - 1)
            root = Tree(self.head.val)
            self.head = self.head.next
            root.left = left
            root.right = helper(mid + 1, end)
            return root
        
        self.head, copy, n = head, head, 0
        while copy:
            copy = copy.next
            n += 1
            
        return helper(0, n-1)