⼆叉树---建⽴⾼度最⼩的⼆叉树
本⽂涉及到的代码可以在中到。
题⽬描述：
对于⼀个元素各不相同且按升序排列的有序序列，请编写⼀个算法，创建⼀棵⾼度最⼩的⼆叉查树。
给定⼀个有序序列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;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。