将升序数组转化为平衡二叉搜索树
问题描述
给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）。平衡二叉搜索树是指树上的每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1。
示例：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
分析问题
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:3494611f-c905-43ec-b120-3c7b3fc6b116
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c0410496-f6c6-46e2-a707-294b4a8b2726
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:68bf4fa2-f389-4f8f-a77a-56bf22f93879
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:68f86504-3d24-44b3-b936-78059b04eb0c
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:1def607e-a7f0-408d-ab9e-5147f6967478
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:dfedc147-6451-4210-82be-15b0ed456977
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:7dde6bf8-996b-4ee6-824e-4c219f70cfa5
[En]
[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e8d9519f-01c3-4c93-9ed5-ebd2c37e48b2
方法一
选择中间位置左边的数字作为根节点，则根节点的下标为 mid=(left+right) // 2。
class Solution:
def sortedArrayToBST(self, nums):
def cur(left, right):
if left > right:
return None
#选择中间位置左边的数字作为根节点
mid = (left + right) // 2
root = TreeNode(nums[mid])
#递归求解左右子树
root.left = cur(left, mid - 1)
root.right = cur(mid + 1, right)
return root
return cur(0, len(nums) - 1)
方法二：
选择中间位置右边的数字作为根节点，则根节点的下标为 mid=(left+right+1) // 2。
class Solution:
def sortedArrayToBST(self, nums):
def cur(left, right):
if left > right:
return None
#选择中间位置右边的数字作为根节点
mid = (left + right + 1) // 2
root = TreeNode(nums[mid])
#递归求解左右子树
root.left = cur(left, mid - 1)
root.right = cur(mid + 1, right)
return root
return cur(0, len(nums) - 1)
方法三
选择任意一个中间位置数字作为根节点，则根节点的下标mid在(left+right)//2 和 (left+right+1)/2 中随机选择一个。
import random
class Solution:
def sortedArrayToBST(self, nums):
def cur(left, right):
if left > right:
return None
#选择中间位置随机一个作为根节点
random_data= random.randint(0, 1)
mid = (left + right + random_data) // 2
root = TreeNode(nums[mid])
#递归求解左右子树
root.left = cur(left, mid - 1)
root.right = cur(mid + 1, right)
return root
return cur(0, len(nums) - 1)
Original: https://www.cnblogs.com/cxyxz/p/15545948.html
Author: 算法推荐管
Title: 将升序数组转化为平衡二叉搜索树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/562435/
转载文章受原作者版权保护。转载请注明原作者出处！