[Leetcode][python]Convert Sorted Array to Binary Search Tree

蛮三刀酱

发布于 2019-03-26 17:10:58

4850

发布于 2019-03-26 17:10:58

文章被收录于专栏：蛮三刀的后端开发专栏蛮三刀的后端开发专栏

题目大意

将一个排序好的数组转换为一颗二叉查找树，这颗二叉查找树要求是平衡的。

知识点

二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查找树；没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

解题思路

由于要求二叉查找树是平衡的。所以我们可以选在数组的中间那个数当树根root，然后这个数左边的数组为左子树，右边的数组为右子树，分别递归产生左右子树就可以了。

注意：如果是偶数个数的数组，那么答案就有多种可能。

这也是为什么我的代码分为奇数偶数判定，而标准答案没用，经过测试，两种代码生成两种不同的答案，并且leetcode系统都能接受。

代码

我提交的

# 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
        if len(nums) == 1:
            return TreeNode(nums[0])
        if len(nums)%2 == 1:
            tree = TreeNode(nums[len(nums)/2])
            tree.left = self.sortedArrayToBST(nums[:(len(nums)/2)])
            tree.right = self.sortedArrayToBST(nums[-(len(nums)/2):])
        else:
            tree = TreeNode(nums[len(nums)/2-1])
            tree.left = self.sortedArrayToBST(nums[:(len(nums)/2)-1])
            tree.right = self.sortedArrayToBST(nums[-(len(nums)/2):])
        return tree

标准代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param num, a list of integers
    # @return a tree node
    def sortedArrayToBST(self, num):
        length = len(num)
        if length == 0:
            return None
        if length == 1:
            return TreeNode(num[0])
        root = TreeNode(num[length / 2])
        root.left = self.sortedArrayToBST(num[:length/2])
        root.right = self.sortedArrayToBST(num[length/2 + 1:])
        return root