将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
思路:递归
先看题目所给出的要求以及限制。
在这里,可以看到有序数组是按照升序排序的。我们知道,二叉搜索树(BST)中序遍历就是升序序列,那么我们可以从这个角度出发,那么问题就转变为从中序遍历的序列中恢复二叉搜索树。
那么任选一个元素作为根节点,以元素左边的序列构建左子树,右边序列构建右子树。
但是由于有限制条件,需要转换为高度平衡二叉树,根据前面给出高度平衡二叉树的概念。那么我们考虑选择数组的中间元素作为根节点来代替前面的任意选择一个元素。
具体的实现代码如下。
# 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: List[int]) -> TreeNode:
def dfs(left, right):
if left > right:
# 表示空子树
return None
# 选取中间元素为根节点
mid = left + (right-left) // 2
root = TreeNode(nums[mid])
# 中间元素左边序列构建左子树
# 右边序列构建右子树
root.left = dfs(left, mid-1)
root.right = dfs(mid+1, right)
return root
return dfs(0, len(nums)-1)
文章原创,如果觉得写得好,欢迎关注点赞。微信公众号《书所集录》,同步更新,同样欢迎关注。
本文地址:https://blog.csdn.net/weixin_45642918/article/details/107109093
如对本文有疑问, 点击进行留言回复!!
老猿学5G:融合计费场景的离线计费会话的Nchf_OfflineOnlyCharging_Release释放操作
老猿学5G扫盲贴:中国移动5G融合计费漫游计费架构和路由方案
老猿学5G扫盲贴:与用户和终端相关的名词UE、SUPI、GPSI、PEI
三星以核心技术优势持续更新折叠手机,华为缺乏自主技术无力应对
基于OpenCV+Python的均值滤波,高斯滤波,中值滤波,双边滤波
网友评论