108. Convert Sorted Array to Binary Search Tree

将一个排序的数组转化为一个二叉搜索树

思路：中间位置的为root, 左半边为左子树，右半边为右子树，递归处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        # 6 star, 没有完全理解
        # 
        if not nums:
            return None
        length = len(nums)
        root = TreeNode(nums[length/2])
        left = self.sortedArrayToBST(nums[:length/2])
        right = self.sortedArrayToBST(nums[length/2+1:])
        root.left, root.right = left, right
        return root

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 6 star, 数组的中间位置的值作为根节点，左节点为左半边数组的中间节点，右节点同理，递归
func sortedArrayToBST(nums []int) *TreeNode {
	length := len(nums)
	if length == 0 {return nil}
	if length == 1 {return &TreeNode{nums[0], nil, nil}}
	mid := length / 2
	node := TreeNode{nums[mid], nil, nil}
	left := sortedArrayToBST(nums[:mid])
	right := sortedArrayToBST(nums[mid+1:])
	node.Left, node.Right = left, right
	return &node

}