0109-convert-sorted-list-to-binary-search-tree-1.py

"""
Similar to #108 Convert Sorted Array to Binary Search Tree, the linked list can be converted to an array in O(n) time,
then it can be converted to BST in O(logn) time.
"""

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        nums = []

        # Convert linked list to array
        while head:
            nums.append(head.val)
            head = head.next

        def buildTree(l, r):
            # Check recursion boundary
            if l > r:
                return None

            # (l + r) // 2 is OK as well, just round up the middle index to be exactly as the official solution
            m = (l + r + 1) // 2
            # Return root node with child nodes recursively built by passing the left and right ranges
            return TreeNode(nums[m], buildTree(l, m-1), buildTree(m+1, r))

        return buildTree(0, len(nums)-1)