LeetCode 108 [Convert Sorted Array to Binary Search Tree]

题目链接

题目描述

  • 给定一个由小到大排好序的数组,要求将每个数组的值作为一个结点的值,将结点构建成一棵平衡的二叉排序树。

解题思路

  • 如果二叉树是平衡的,则它的任意一个结点的左子树和右子树的高度差不超过1
  • 数组是由小到大有序的,可以考虑用二分法找到中间元素作为根结点的值,再把根结点的左右两边看成两个子数组,左子数组的元素都比根结点的值小,右子数组的元素都比根结点的值大。若原数组的元素个数是奇数,那么根结点的值刚好是位于中间的元素,左右子数组的元素个数相同;若原数组的元素个数是偶数,那么根结点的值则是中间偏左的元素或中间偏右的元素,左右子数组的元素个数差值为1。继续对左右子数组进行递归处理,直到不能再划分
  • 用这种方法,最后一层得到树必然是平衡的,根结点的父结点对应的树也是平衡的,进而可以推断出最终构建出来的二叉树是二叉平衡树。另外,在每次构建过程中都可以保证左子树的所有结点的值都比根结点小,右子树的所有结点的值都比根结点大,因此最终构建出来的二叉树是二叉排序树
  • 若原数组元素个数为n,则处理过程的时间复杂度为O(log n)

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* 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;
}
};