3.2 如何把一个有序整数数组放到二叉树中

难度系数：★★★★☆

被考查系数：★★★☆☆

分析与解答：

如果要把一个有序的整数数组放到二叉树中，那么所构造出来的二叉树必定也是一棵有序的二叉树。鉴于此，实现思路为：取数组的中间元素作为根结点，将数组分成左右两部分，对数组的两部分用递归的方法分别构建左右子树。如下图所示。

如上图所示，首先取数组的中间结点6作为二叉树的根结点，把数组分成左右两部分，然后对于数组的左右两部分子数组分别运用同样的方法进行二叉树的构建，例如，对于左半部分子数组，取中间结点3作为树的根结点，再把孩子数组分成左右两部分。依此类推，就可以完成二叉树的构建，实现代码如下：

程序的运行结果为

算法性能分析：

由于这种方法只遍历了一次数组，因此，算法的时间复杂度为O(n)，其中，N表示的是数组长度。