将有序数组转换为平衡二叉搜索树

将有序数组转换为平衡二叉搜索树

问题

给定一个有序数组，数组元素升序排列，试将该数组转换为一棵平衡二叉搜索树（Balanced Binary Search Tree）。

思路

这个问题用递归很容易解出来。考虑下面一棵二叉搜索树：

这是一棵平衡的二叉搜索树，所谓平衡的定义，就是指二叉树的子树高度之差不能超过1。

如果要从一个有序数组中选择一个元素作为根结点，应该选择哪个元素呢？我们应该选择有序数组的中间元素作为根结点。

选择了中间元素作为根结点并创建后，剩下的元素分为两部分，可以看作是两个数组。这样剩下的元素在根结点左边的作为左子树，右边的作为右子树。、

解法

由上面的思路，我们可以在O（N）的时间内从有序数组创建一棵平衡的BST，使用分治算法，代码如下：

Cpp代码  

1. struct node* sortedArrayToBST(int arr[], int start, int end)   
2. {  
3.   if (start > end) return NULL;  
4.   // 这里同（start+left）/2，目的是为了防止溢出.  
5.   int mid = start + (end - start) / 2;  
6.   struct node *root = newNode(arr[mid]);//newNode创建二叉树结点，具体代码请看文章 二叉树问题汇总（1）  
7.   root->left = sortedArrayToBST(arr, start, mid-1);  
8.   root->right = sortedArrayToBST(arr, mid+1, end);  
9.   return root;  
10. }  
11.    
12. struct node* sortedArrayToBST(int arr[], int n)   
13. {  
14.   return sortedArrayToBST(arr, 0, n-1);  
15. }  

英文原文地址：http://www./2010/11/convert-sorted-array-into-balanced.html