108. Convert Sorted Array to Binary Search [Python]

zluxingzhe 2020-02-29

108. Convert Sorted Array to Binary Search

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

给定一个升序的矩阵,将它转换成一棵平衡二叉树。

其中,平衡二叉树是指树中每个节点子树高度差的绝对值不超过1的树。

思路:由于左右高度差的绝对值不能超过1,所以树根节点应选择升序列表中间的元素,即nums[len(nums)//2]。

该元素前面的元素(比根节点小的元素)同理递归地放入左子树;后面的元素递归地放入右子树。

最后返回各个节点。

代码

class Solution:
    def sortedArrayToBST(self, nums):
        """
        @param type nums: List[int]
        @param rtype: TreeNode
        """
        if nums == None:
            return
        if len(nums) == 1:
            return nums[0]
        root = nums[len(nums)//2]
        self.sortedArrayToBST(nums[:len(nums)//2])
        self.sortedArrayToBST(nums[len(nums)//2+1:])
        return root

相关推荐