108. Convert Sorted Array to Binary Search Tree

solution108.py

# https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return
        
        def createBST(nums):
            if not nums:
                return
            length = len(nums)
            midpoint = length // 2
            
            if length % 2 == 0:
                midpoint -= 1
                
            node = ListNode(nums[midpoint])
            node.left = createBST(nums[:midpoint])
            node.right = createBST(nums[midpoint+1:])
            
            return node
        
        def tree_to_array(node):
            q = [node]
            ans = []
            while q:
                length = len(q)
                
                for i in range(length):
                    temp = q[i]
                    if temp:
                        ans.append(temp.val)
                        q.append(temp.left)
                        q.append(temp.right)
                    else:
                        ans.append(None)
                        
                q = q[length:]
            
            while ans[-1] == None:
                del ans[-1]
            
            return ans
        
        root = createBST(nums)

        return tree_to_array(root)