题目:将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例:
解题思路思路:递归 先看题目所给出的要求以及限制。
在这里,可以看到有序数组是按照升序排序的。我们知道,二叉搜索树(BST)中序遍历就是升序序列,那么我们可以从这个角度出发,那么问题就转变为从中序遍历的序列中恢复二叉搜索树。 那么任选一个元素作为根节点,以元素左边的序列构建左子树,右边序列构建右子树。 但是由于有限制条件,需要转换为高度平衡二叉树,根据前面给出高度平衡二叉树的概念。那么我们考虑选择数组的中间元素作为根节点来代替前面的任意选择一个元素。 具体的实现代码如下。 代码实现
实现结果总结
|
|
来自: 千锋Python学堂 > 《Python基础教程分享》