题目描述
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
示例:
1
2
3
4
5
6
7
8
9
| 给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
|
算法
已知有一个升序 有序的 整数数组，要构造一棵高度最小的二叉搜索树。
根据二叉搜索树的定义可知：分支节点上的值大于左子树上节点的值，小于右子树上节点的值，且二叉搜索树上的没有健值相等的节点。
高度最小则需要符合完全二叉树的特点。
因此可以使用 递归+二分法 从整数数组里逐个取出节点，构成一个二叉树。
递归+二分法
递归+二分法 的重点在于边界值的确定。
- [0,numsSize-1]
左右边界值分别是数组开始索引的和结束索引，每次取出中间值后，数组分成了三部分：[0,mid-1],mid,[mid+1,numsSize-1]。再分别对左右两个数组递归调用。结束递归的条件是数组的左边索引值 $l$ 大于 右边索引值 $r$。
1
2
3
4
5
6
7
8
9
10
| struct TreeNode* recursionsortedarray_2(int* nums, int l, int r)
{
if (l > r) return NULL;
int mid = (l + r) / 2;
struct TreeNode* root = creatnewnode(nums[mid]);
root->left = recursionsortedarray_2(nums, l, mid-1);
root->right = recursionsortedarray_2(nums, mid + 1, r);
return root;
}
|
- [0,numsSize]
左右边界值分别是数组开始索引的和数组数量，每次取出中间值后，数组分成了三部分：[0,mid],mid,[mid+1,numsSize]。再分别对左右两个数组递归调用。结束递归的条件是数组的左边索引值 $l$ 大于等于 右边索引值 $r$。
1
2
3
4
5
6
7
8
9
10
| struct TreeNode* recursionsortedarray(int* nums, int l, int r)
{
if (l >= r) return NULL;
int mid = (l + r) / 2;
struct TreeNode* root = creatnewnode(nums[mid]);
root->left = recursionsortedarray(nums, l, mid);
root->right = recursionsortedarray(nums, mid + 1, r);
return root;
}
|
两种方法都可以得到一个高度 $h$ 一样的二叉树，但是第一种的到的结果不符合完成二叉树，所以应该采用第二种边界值方法。
C代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode *creatnewnode(int num)
{
struct TreeNode* temp = malloc(sizeof(struct TreeNode));
temp->right = NULL;
temp->left = NULL;
temp->val = num;
return temp;
}
struct TreeNode* recursionsortedarray(int* nums, int l, int r)
{
if (l >= r) return NULL;
int mid = (l + r) / 2;
struct TreeNode* root = creatnewnode(nums[mid]);
root->left = recursionsortedarray(nums, l, mid);
root->right = recursionsortedarray(nums, mid + 1, r);
return root;
}
struct TreeNode* sortedArrayToBST(int* nums, int numsSize)
{
return recursionsortedarray(nums, 0, numsSize);
}
void disTree(struct TreeNode* T)
{
if(T != NULL)
{
printf("%d",T->val);
if(T->left != NULL || T->right != NULL)
{
printf("(");
if(T->left != NULL)
{
disTree(T->left);
}
if(T->right != NULL)
{
printf(",");
disTree(T->right);
}
printf(")");
}
}
}
int main()
{
int nums[10] = {1,3,5,7,9,11,13,15,17,19};
int numsSize = 10;
struct TreeNode* T = sortedArrayToBST(nums,numsSize);
disTree(T);
return 0;
}
|