【牛客刷题 - 算法】NC11 将升序数组转化为平衡二叉搜索树

作者：清风莫追

2022 年 10 月 03 日
湖南
本文字数：1201 字
阅读完需：约 4 分钟

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

@[toc]

1.题目描述

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

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

数据范围： $100000 \leq n \leq 10000$ ，数组中每个值满足 $∣ v a l ∣ \leq 5000$ 进阶：空间复杂度 $O (n) O (n)$ ，时间复杂度 $O (n) O (n)$

例如当输入的升序数组为 $[- 1, 0, 1, 2]$ 时，转化后的平衡二叉搜索树（BST）可以为 $1, 0, 2, - 1$ ，如下图所示：

或为 ${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.运行结果

成功通过！

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！👉点击开始刷题学习👈

感谢阅读

个人主页：清风莫追

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/20f235c15ff11d866cac23fce】。文章转载请联系作者。

清风莫追

关注

还未添加个人签名 2022.08.09 加入

编程一学生

发布

暂无评论

创作场景