【IT笔试面试题整理】有序数组生成最小高度二叉树

【试题描述】定义一个函数，输入一个有序数组生成最小高度二叉树

We will try to create a binary tree such that for each node, the number of nodes in the left
subtree and the right subtree are equal, if possible
Algorithm:
1   Insert into the tree the middle element of the array
2   Insert (into the left subtree) the left subarray elements
3   Insert (into the right subtree) the right subarray elements
4   Recurse

【参考代码】

 1     public static Node addToTree(int[] arr,int start,int end)
 2     {
 3         if(end < start)
 4             return null;
 5         int mid = (start + end)/2;
 6         Node n = new Node(arr[mid]);
 7         n.left = addToTree(arr,start,mid-1);
 8         n.right = addToTree(arr,mid+1,end);
 9         return n;
10     }
11     public static Node createMinBST(int[] array)
12     {
13         return addToTree(array,0,array.length - 1);
14     }