current position:Home>[Niu Ke brush question-algorithm] NC11 converts an ascending array into a balanced binary search tree

[Niu Ke brush question-algorithm] NC11 converts an ascending array into a balanced binary search tree

2022-09-23 10:02:23Don't chase the breeze

个人主页:清风莫追
系列专栏:牛客刷题——数据结构与算法
推荐一款面试、刷题神器牛客网Click to join the quiz army


1.题目描述

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

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

数据范围 100000 ≤ n ≤ 10000 100000≤n≤10000 100000n10000,数组中每个值满足 ∣ v a l ∣ ≤ 5000 ∣val∣≤5000 val5000
进阶:空间复杂度 O ( n ) O ( n ) O(n)O(n) O(n)O(n),时间复杂度 O ( n ) O ( n ) O(n)O(n) O(n)O(n)

例如When the input ascending array is [ − 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.算法设计思路

We only need to construct a corresponding binary tree according to the array parameters and return the root node.首先我们要注意到:输入的数组是升序的.

于是我们只要:

  1. 选择数组的中间元素作为根结点
  2. Take the remaining elements to the left of the middle element,Build the left subtree
  3. Take the remaining elements to the right of the middle element,Build the right subtree

The corresponding balanced binary tree can be constructed recursively.

3.算法实现

注:这里并不是完整代码,而只是核心代码的模式

1)遇到的一些问题

在具体的实现时,There will also be some details handling issues.例如:

  • When two array elements are needed to build a subtree,and cannot be further divided into左子树根结点右子树三个部分
  • The given function declarationsortedArrayToBST(int* num, int numLen )The argument list does not satisfy our recursive needs

And a stupid onebug卡了我好久,就是把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.运行结果

成功通过!

在这里插入图片描述


结束语:

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

在这里插入图片描述


感谢阅读

个人主页:清风莫追

CSDN话题挑战赛第2期
参赛话题:学习笔记

copyright notice
author[Don't chase the breeze],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/266/202209230952372517.html

Random recommended