一点一点前进...

0%

有序数组生成高度最小的二叉搜索树

给一个有序的数组,升序,没有重复的数字,生成一个高度最小的二叉搜索树。

二叉搜索树具有的特点就是左边节点的值比当前节点的小,右边节点的值比当前节点的大。而一个有序数组,恰恰是二叉搜索树的中序遍历结果。
扯了点没用的,想要高度低,就要尽可能的平衡,左右两个子树尽可能的平衡,那么,数组中间的数就是根节点了。左边的树就是数组中间左边的半个数组组成的,右边的树就是数组右边的半个数组组成的。这一段描述,是一个递归的过程,按照这个思路,代码也就有了。

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
class TreeNode<T>
{
public TreeNode<T> Left { get; set; }
public TreeNode<T> Right { get; set; }
public T Data { get; set; }
}

static TreeNode<T> CreateMinimalBst<T>(T[] arr, int begin, int end)
{
if (begin > end)
{
return null;
}

int mid = (end - begin) / 2 + begin;
var node = new TreeNode<T>();
node.Data = arr[mid];
node.Left = CreateMinimalBst(arr, begin, mid - 1);
node.Right = CreateMinimalBst(arr, mid + 1, end);

return node;
}

static TreeNode<T> CreateMinimalBst<T>(T[] arr)
{
return CreateMinimalBst(arr, 0, arr.Length - 1);
}

O(n)的时间复杂度就搞定了这个题目,空间复杂度呢?表面看来,没有使用额外的存储空间,但是递归导致栈空间的增长,O(lg(n))。