将有序数组转换为二叉搜索树
本文最后更新于:2022年11月30日 晚上
每日第三题,今天的事情做完了,来刷道题爽一下
将有序数组转换为二叉搜索树
解题思路
还是一样的,先确定二叉树的递归框架,二叉搜索树无非就是左子树小于根节点、右子树大于根节点,而满足高度平衡我们可以选择数组的中间元素作为根节点,这样左子树和右子树的就是高度平衡的。
说完这两个条件大家都应该明白了,我们需要选择数组的中间元素作为根节点,之后再选取小于根节点的数据做左子树,大于根节点的数据做右子树,这不就是前序遍历嘛!!!即我们最先确定根节点,再去遍历左右子树。
好了,书写递归最重要的一步我们确定了,接下来就可以确定递归的终止条件了,可以知道当数组为空的时候就没办法生成树了。所以终止条件就是数组为空
代码
1 |
|
写在最后
我们可是要成为卷王的男人QuQ
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!