C语言面试题之最小高度树
最小高度树
实例要求
- 1、给定一个有序整数数组,元素各不相同且按升序排列;
- 2、编写一个算法,创建
一棵高度最小的二叉搜索树
; - 示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
实例分析
- 一、算法思想:
- 使用
递归
来实现将有序数组转换为二叉搜索树
; - 二、具体步骤:
- 1、找到数组的中间元素,将其作为根节点;
- 2、将数组分成左右两部分,分别
递归地构建左子树和右子树
; - 3、返回根节点;
示例代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* sortedArrayToBSTUtil(int* nums, int start, int end) {
if (start > end) {
return NULL;
}
int mid = start + (end - start) / 2; // 找到中间元素的索引
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = nums[mid]; // 中间元素作为根节点的值
root->left = sortedArrayToBSTUtil(nums, start, mid - 1); // 递归构建左子树
root->right = sortedArrayToBSTUtil(nums, mid + 1, end); // 递归构建右子树
return root;
}
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
if (numsSize == 0) {
return NULL;
}
return sortedArrayToBSTUtil(nums, 0, numsSize - 1);
}
运行结果
原文地址:https://blog.csdn.net/qq_41878292/article/details/137545446
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!