首页设计公司_宁波seo深度优化平台_网络推广公司经营范围_百度网站推广费用

题目：

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

示例：

给定有序数组: [-10,-3,0,5,9],一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：0 / \ -3   9 /   / -10  5 

思路：

1. 首先，你需要了解什么是二叉搜索树。可以看这篇文章。数据结构——二叉搜索树-CSDN博客
2. 现在我们知道了的二叉搜索树的定义后，不难发现，对该数中序遍历即可得到升序序列。
3. 如何才能是最小高度呢？这得保证左子树和右子树的节点数尽量差不多，因此，序列的中位数必须是根节点，偶数时，两个中位数选哪个都行，我选中点右边的那一个。
4. 采用递归的方法，根节点的左子树的根节点也是左边序列的中位数，右子树同理。最后即可得出最小高度二叉搜索树。

C代码如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/struct TreeNode* FindRoot(int* nums, int left, int right){if(left > right){return NULL;}// 找到中间节点int mid = (left + right + 1) / 2;struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root -> val = nums[mid];root -> left = FindRoot(nums, left, mid - 1);root -> right = FindRoot(nums, mid + 1, right);return root;
}struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {return FindRoot(nums, 0, numsSize - 1);
}