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

2022-09-23 10:02:23

# 1.题目描述  # 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）遇到的一些问题

• 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期