题目链接
题目描述
- 给定一个由小到大排好序的数组，要求将每个数组的值作为一个结点的值，将结点构建成一棵平衡的二叉排序树。
解题思路
- 如果二叉树是平衡的，则它的任意一个结点的左子树和右子树的高度差不超过1。
- 数组是由小到大有序的，可以考虑用二分法找到中间元素作为根结点的值，再把根结点的左右两边看成两个子数组，左子数组的元素都比根结点的值小，右子数组的元素都比根结点的值大。若原数组的元素个数是奇数，那么根结点的值刚好是位于中间的元素，左右子数组的元素个数相同；若原数组的元素个数是偶数，那么根结点的值则是中间偏左的元素或中间偏右的元素，左右子数组的元素个数差值为1。继续对左右子数组进行递归处理，直到不能再划分。
- 用这种方法，最后一层得到树必然是平衡的，根结点的父结点对应的树也是平衡的，进而可以推断出最终构建出来的二叉树是二叉平衡树。另外，在每次构建过程中都可以保证左子树的所有结点的值都比根结点小，右子树的所有结点的值都比根结点大，因此最终构建出来的二叉树是二叉排序树。
- 若原数组元素个数为n，则处理过程的时间复杂度为O(log n)。
C++代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return convert(nums, 0, nums.size() - 1);
}
TreeNode* convert(vector<int>& nums, int begin, int end) {
if (begin > end) {
return NULL;
}
if (begin == end) {
return new TreeNode(nums[begin]);
}
int mid = ((begin + end) >> 1);
TreeNode* node = new TreeNode(nums[mid]);
node->left = convert(nums, begin, mid - 1);
node->right = convert(nums, mid + 1, end);
return node;
}
};