个人主页：清风莫追
系列专栏：牛客刷题——数据结构与算法
推荐一款面试、刷题神器牛客网：👉点击加入刷题大军👈

文章目录

1.题目描述
2.算法设计思路
3.算法实现
- 1）遇到的一些问题
- 2）具体代码
4.运行结果
结束语：

1.题目描述

描述
给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.

平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1

数据范围：

100000

≤

10000

100000≤n≤10000

$100000 \leq n \leq 10000$ ，数组中每个值满足

∣

≤

5000

∣val∣≤5000

$∣ v a l ∣\leq 5000$
进阶：空间复杂度

(

)

(

)

O(n)O(n)

$O (n) O (n)$ ，时间复杂度

(

)

(

)

O(n)O(n)

$O (n) O (n)$

例如当输入的升序数组为

[

−

]

[-1,0,1,2]

$[- 1, 0, 1, 2]$ 时，转化后的平衡二叉搜索树（BST）可以为

{

−

}

\{1,0,2,-1\}

${1, 0, 2, - 1}$ ，如下图所示：

或为

{

−

}

\{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;
}