python数据结构（将有序数组转换为二叉搜索树）

1、题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树（BST）。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

2、代码详解

附：此题提交时必须注释掉class TreeNode类

法一：中序遍历，总是选择中间位置左边的数字作为根节点

# 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
        """
        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)  # 写成helper返回 

时间复杂度：O(n)，其中 n 是数组的长度。每个数字只访问一次。

空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(logn)。

二叉搜索树的中序遍历结果为递增序列。现在题目给了我们一个递增序列，要求我们构造一棵二叉搜索树，就是要实现这一特性的逆过程。

中序遍历的顺序为：左节点 → 根节点 → 右节点。

构造一棵树的过程可以拆分成无数个这样的子问题：构造树的每个节点以及节点之间的关系。对于每个节点来说，都需要：

• 选取节点
• 构造该节点的左子树
• 构造该节点的右子树

要求构造一棵「高度平衡」的树，所以我们在选取节点时选择数组的中点作为根节点，以此来保证平衡性。

法一类似写法（没写helper函数）

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

class Solution:
    def sortedArrayToBST(self, nums):
        if not nums:
            return None
        
        # 找到中点作为根节点
        mid = len(nums) // 2
        node = TreeNode(nums[mid])

        # 左侧数组作为左子树
        left = nums[:mid]
        right = nums[mid+1:]

        # 递归调用
        node.left = self.sortedArrayToBST(left)
        node.right = self.sortedArrayToBST(right)

        return node 

本文地址：https://blog.csdn.net/IOT_victor/article/details/107111399