Skip to content

Files

Latest commit

Jan 12, 2019
bfeb428 · Jan 12, 2019

History

History
40 lines (36 loc) · 1.14 KB

108.md

File metadata and controls

40 lines (36 loc) · 1.14 KB

108. Convert Sorted Array to Binary Search Tree

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

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

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:

// 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

}