leetcode

Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

Recursive 递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 None
        i = len(nums) / 2
        node = TreeNode(nums[i])
        node.left = self.sortedArrayToBST(nums[:i])
        node.right = self.sortedArrayToBST(nums[i+1:])
        return node

test code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
      0
     / \
   -3   9
   /   /
 -10  5
In [1]: class TreeNode(object):
   ...:     def __init__(self, x):
   ...:         self.val = x
   ...:         self.left = None
   ...:         self.right = None
   ...:
In [42]: s = Solution(); t = s.sortedArrayToBST([-10,-3,0,5,9])

Iteratively 非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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
        """
        def helper(left, right):
            if left > right:
                return None
            idx = (left + right) / 2
            node = TreeNode(nums[idx])
            node.left = helper(left, idx - 1)
            node.right = helper(idx + 1, right)
            return node
        return helper(0, len(nums) - 1)

test code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-10,5,null,-3,null,9]
      0
     / \
   -10   5
      \   \
      -3    9
In [1]: class TreeNode(object):
   ...:     def __init__(self, x):
   ...:         self.val = x
   ...:         self.left = None
   ...:         self.right = None
   ...:
In [58]: s = Solution(); t = s.sortedArrayToBST([-10,-3,0,5,9])

leet code