本文共 841 字,大约阅读时间需要 2 分钟。
给定一个有序数组,数组元素升序排列,试将该数组转换为一棵平衡二叉搜索树(Balanced Binary Search Tree)。
这个问题用递归很容易解出来。考虑下面一棵二叉搜索树:
这是一棵平衡的二叉搜索树,所谓平衡的定义,就是指二叉树的子树高度之差不能超过1。
如果要从一个有序数组中选择一个元素作为根结点,应该选择哪个元素呢?我们应该选择有序数组的中间元素作为根结点。
选择了中间元素作为根结点并创建后,剩下的元素分为两部分,可以看作是两个数组。这样剩下的元素在根结点左边的作为左子树,右边的作为右子树。、
由上面的思路,我们可以在O(N)的时间内从有序数组创建一棵平衡的BST,使用分治算法,代码如下:
struct node* sortedArrayToBST(int arr[], int start, int end) { if (start > end) return NULL; // 这里同(start+left)/2,目的是为了防止溢出. int mid = start + (end - start) / 2; struct node *root = newNode(arr[mid]);//newNode创建二叉树结点,具体代码请看文章 二叉树问题汇总(1) 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);}英文原文地址:http://www.leetcode.com/2010/11/convert-sorted-array-into-balanced.html
转载地址:http://jnnvi.baihongyu.com/