有序数组创建一棵平衡的BST

本文主要是介绍有序数组创建一棵平衡的BST，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如果要从一个有序数组中选择一个元素作为根结点，应该选择哪个元素呢？我们应该选择有序数组的中间元素作为根结点。
选择了中间元素作为根结点并创建后，剩下的元素分为两部分，可以看作是两个数组。这样剩下的元素在根结点左边的作为左子树，右边的作为右子树。

解法

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

struct node* sortedArrayToBST(int arr[], int start, int end)   
{  if (start > end) return NULL;   int mid = start + (end - start) / 2;  struct node *root = newNode(arr[mid]);root->left = sortedArrayToBST(arr, start, mid-1);  root->right = sortedArrayToBST(arr, mid+1, end);  return root;  
}  struct node* sortedArrayToBST(int arr[], int n)   
{  return sortedArrayToBST(arr, 0, n-1);  
}  

这篇关于有序数组创建一棵平衡的BST的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---