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

╰半夏微凉° 2022-06-11 00:13 116阅读 0赞

## 题目大意 ##

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

### 知识点 ###

二叉查找树（英语：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

## 总结 ##

1.  已经做了很多**递归**的题目了，这种解题结构已经定型了，很多题目都可以这样套
2.  切片