写点什么

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

作者:清风莫追
  • 2022 年 10 月 03 日
    湖南
  • 本文字数:1201 字

    阅读完需:约 4 分钟

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

csdn 个人主页:清风莫追

系列专栏:牛客刷题——数据结构与算法推荐一款面试、刷题神器牛客网:👉点击加入刷题大军👈


@[toc]



1.题目描述

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


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


数据范围,数组中每个值满足 进阶:空间复杂度 ,时间复杂度


例如当输入的升序数组为时,转化后的平衡二叉搜索树(BST)可以为,如下图所示:


或为 {0,-1,1,#,#,#,2} ,如下图所示:


返回任意一种即可。

2.算法设计思路

我们只需根据数组参数构建出一颗相应的二叉树并返回根结点即可。首先我们要注意到:输入的数组是升序的


于是我们只要:


  1. 选择数组的中间元素作为根结点

  2. 以中间元素左边的剩余元素,构建出左子树

  3. 以中间元素右边的剩余元素,构建出右子树


便可以递归地构建出相应的平衡二叉树。

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
用户头像

清风莫追

关注

还未添加个人签名 2022.08.09 加入

编程一学生

评论

发布
暂无评论
【牛客刷题-算法】NC11 将升序数组转化为平衡二叉搜索树_数据结构_清风莫追_InfoQ写作社区