将升序数组转化为平衡二叉搜索树

[编程题]将升序数组转化为平衡二叉搜索树

热度指数：32617 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

数据范围： $0 \le n \le 10000$ ，数组中每个值满足 $|val| \le 5000$
进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

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

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

返回任意一种即可。

示例1

输入

[-1,0,1,2]

输出

{1,0,2,-1}

示例2

输入

[]

输出

{}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

80后大叔

平衡二叉树的根一定是numLen/2，所以先创建root节点，然后分别创建左右子节点即可

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @return TreeNode类
 */
struct TreeNode* sortedArrayToBST(int* num, int numLen ) {
    // write code here
    if(numLen==0){
        return NULL;
    }
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = num[numLen/2];
    struct TreeNode* left1 = root;
    struct TreeNode* left2 = root;
    struct TreeNode* right1 = root;
    struct TreeNode* right2 = root;
    int left=numLen/2-1, right=numLen/2+1;
    while(left >= 0) {
        left2 = malloc(sizeof(struct TreeNode));
        left2->val = num[left];
        left2->left = NULL;
        left2->right = NULL;
        left1->left = left2;
        left1 = left2;
        left--;
    }
    while(right <= numLen-1) {
        right2 = malloc(sizeof(struct TreeNode));
        right2->val = num[right];
        right2->right = NULL;
        right2->left = NULL;
        right1->right = right2;
        right1 = right2;
        right++;
    }
    return root;
}

发表于 2022-11-04 11:50:12 回复(0)

上班使我摸鱼

以数组中数为根创建一个平衡二叉树

/**

* struct TreeNode {
*    int val;
*    struct TreeNode *left;
*    struct TreeNode *right;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num int整型一维数组
* @param numLen int num数组长度
* @return TreeNode类
*/
typedef struct TreeNode AVLNode;
AVLNode* create(int** num,int left,int right){
if(left>right)return NULL;
int mid=(left+right)/2;
AVLNode* x=(AVLNode*)malloc(sizeof(AVLNode));
x->val=(*num)[mid];
x->left=create(num,left,mid-1);
x->right=create(num,mid+1,right);
return x;
}
struct TreeNode* sortedArrayToBST(int* num, int numLen ) {
// write code here
AVLNode* root=create(&num,0,numLen-1);
return root;
}

发表于 2022-07-16 15:20:17 回复(0)