1.题目描述
描述
给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.
平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1
数据范围：100000 ≤ n ≤ 10000 100000≤n≤10000100000≤n≤10000，数组中每个值满足 ∣ v a l ∣ ≤ 5000 ∣val∣≤5000∣val∣≤5000
进阶：空间复杂度 O ( n ) O ( n ) O(n)O(n)O(n)O(n)，时间复杂度 O ( n ) O ( n ) O(n)O(n)O(n)O(n)
例如当输入的升序数组为[ − 1 , 0 , 1 , 2 ] [-1,0,1,2][−1,0,1,2]时，转化后的平衡二叉搜索树（BST）可以为{ 1 , 0 , 2 , − 1 } \{1,0,2,-1\}{1,0,2,−1}，如下图所示：
或为 { 0 , − 1 , 1 , # , # , # , 2 } \{0,-1,1,\#,\#,\#,2\}{0,−1,1,#,#,#,2} ，如下图所示：
返回任意一种即可。
2.算法设计思路
我们只需根据数组参数构建出一颗相应的二叉树并返回根结点即可。首先我们要注意到：输入的数组是升序的。
于是我们只要：
选择数组的中间元素作为根结点
以中间元素左边的剩余元素，构建出左子树
以中间元素右边的剩余元素，构建出右子树
便可以递归地构建出相应的平衡二叉树。
3.算法实现
注：这里并不是完整代码，而只是核心代码的模式
1）遇到的一些问题
在具体的实现时，还会碰到一些细节处理上的问题。例如：
当需要用两个数组元素来构建一颗子树时，并不能再划分为左子树、根结点、右子树三个部分
已给出的函数声明sortedArrayToBST(int* num, int numLen )的参数列表并不能满足我们递归的需求
还有一个愚蠢的bug卡了我好久，就是把e - f写成了f - e。
2）具体代码
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型一维数组 * @param numLen int num数组长度 * @return TreeNode类 */ struct TreeNode* create(int* num, int f, int e){ struct TreeNode* root = (struct TreeNode *)malloc(sizeof(struct TreeNode)); if(e - f == 0){ root->val = num[f]; root->left = NULL; root->right = NULL; } else if(e - f == 1){ root->val = num[f]; root->left = NULL; root->right = create(num, e, e); } else { int mid = (f + e) / 2; root->val = num[mid]; //num[mid] = 9; root->left = create(num, f, mid-1); root->right = create(num, mid+1, e); } return root; } struct TreeNode* sortedArrayToBST(int* num, int numLen ) { // write code here struct TreeNode* root = NULL; if(numLen == 0){ return NULL; } root = create(num, 0, numLen-1); return root; }
4.运行结果
成功通过！
