二叉树---建立高度最小的二叉树

本文涉及到的代码可以在我的github中找到。 题目描述：

对于一个元素各不相同且按升序排列的有序序列，请编写一个算法，创建一棵高度最小的二叉查找树。 给定一个有序序列int[] vals,请返回创建的二叉查找树的高度。

分析：

这里题目只是要求返回二叉树的高度，虽然我们可以用公式直接算出来，不过我们是出于练习的目的，因此我们这里也建个树。

首先使用公式计算的方法的一种代码：

package newcoder; import java.util.*; public class MinimalBST { public int buildMinimalBST(int[] vals) { // write code here int length = vals.length; int count = 0; while (length != 1) { length = length >> 1; count++; } return ++count; } }

下面我们实实在在的建立一个BST，并计算他的高度。

public Node getMiniBst(int[] vals, int start, int end) { if (start > end)//start==end的情况也是一层节点，因此不能加入这个条件。 { return null; } int mid = start + (end - start) / 2; Node root = new Node(vals[mid]); root.left = getMiniBst(vals, start, mid - 1);//构建左子树 root.right = getMiniBst(vals, mid + 1, end);//构建右子树 return root; }