LeetCode-Python/ConvertSortedArray2BinarySearchTree.py at master · summer-liu/LeetCode-Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 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 len(nums) == 0:
    #     	return None
    #     return self.middleNode(nums, 0, len(nums)-1)
    # def middleNode(self, num, start, end):
    # 	if start > end:
    # 		return None
    # 	root = TreeNode(num[start + (end-start)/2])
    # 	root.left = self.middleNode(num, start, start+(end-start)/2-1)
    # 	root.right = self.middleNode(num, start+(end-start)/2+1, end)
    # 	return root
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if len(nums) == 0:
        	return None
        elif len(nums) == 1:
        	return TreeNode(nums[0])
        else:
        	mid = len(nums)/2
        	root = TreeNode(nums[mid])
        	root.left = self.sortedArrayToBST(nums[:mid])
        	root.right = self.sortedArrayToBST(nums[mid+1:])
        return root