LeetCode 108. 将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树

题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

链接 https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

个人思路

1. 本来是想完成一个比较简单的高度平衡二叉搜索树：即取中间位置的数作为根结点，然后对其左右两边的数分别使用指针，左边加入左子树，右边都加入右子树，即对于[0,1,2,3,4,5]
   ，我构建如下的树，
   

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        numsLen = len(nums)
        if numsLen == 1:
            return TreeNode(nums[0])
        mid = numsLen // 2 
        left = mid - 1
        right = mid + 1
        root = TreeNode(nums[mid])
        temp = root
        while left >= 0:
            temp.left = TreeNode(nums[left])
            left -= 1
            temp = temp.left
        temp = root
        while right < numsLen:
            temp.right = TreeNode(nums[right])
            right += 1
            temp = temp.right
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

但却在该测试用例时候输出结果是[3,2,4,1,null,null,5,0]（应该就是我设想的结果），与答案预期结果不同[3,1,5,0,2,4]。难道是上图这种不是 高度平衡 二叉搜索树 ？

官方思路

前言：二叉搜索树的中序遍历是升序序列，题目给定的数组是按照升序排序的有序数组，因此可以确保数组是二叉搜索树的中序遍历序列。

1. 中序遍历，总是选择中间位置左边的数字作为根节点
   选择中间位置左边的数字作为根节点，则根节点的下标为 mid=(left+right)//2。

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None

            # 总是选择中间位置左边的数字作为根节点
            mid = (left + right) // 2

            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

        return helper(0, len(nums) - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. 中序遍历，总是选择中间位置右边的数字作为根节点
   选择中间位置右边的数字作为根节点，则根节点的下标为 mid=(left+right+1)//2，此处的除法为整数除法。

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None

            # 总是选择中间位置右边的数字作为根节点
            mid = (left + right + 1) // 2

            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

        return helper(0, len(nums) - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3. 中序遍历，选择任意一个中间位置数字作为根节点
   选择任意一个中间位置数字作为根节点，则根节点的下标为 2mid=(left+right)//2 和 mid=(left+right+1)//2 两者中随机选择一个，此处的除法为整数除法。

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None

            # 选择任意一个中间位置数字作为根节点
            mid = (left + right + randint(0, 1)) // 2

            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root

        return helper(0, len(nums) - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

复杂度分析
时间复杂度：O(n)，其中 n 是数组的长度。每个数字只访问一次。
空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(logn)。

参考：
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/solution/jiang-you-xu-shu-zu-zhuan-huan-wei-er-cha-sou-s-33/