题目要求:给定一个升序排列的一维数组,根据这个数组生成一颗高度平衡的二叉排序树。
例如A=[1,2,3,4,5,6,7,8];
思想:使用二分法来求解。
数组的low,high,middle分别指向当前范围内数组的最低位、最高位和中间位置。middle位置处付给当前树的树根,[low,middle-1]的节点都是当前树的左子树节点,[middle+1,high]的节点都是当前树的右子树节点,……如此循环直到low不再大于high为止。
也就是
当low<high时,左右子树继续二分;
当low == high时,此时的节点为叶子节点,返回叶子节点;
当low>high时,此时无节点,返回空。
另外,还有特殊情况也需要考虑,当给的数组为空时的处理。
代码如下。