题目描述
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
题解
转化的结果是不唯一的。不过代码写好了转换出来就是唯一的了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| TreeNode* ArrayToBST(vector<int>& nums,int left,int right) {
if (left == right)return NULL;
if (left == right - 1)return new TreeNode(nums[left]);
int mid = (left + right) / 2;
TreeNode* root= new TreeNode(nums[mid]);
root->left = ArrayToBST(nums, left, mid);
root->right = ArrayToBST(nums, mid+1, right);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
int vsize = nums.size();
if (!vsize)return NULL;
if(vsize==1)return new TreeNode(nums[0]);
return ArrayToBST(nums, 0, vsize);
}
|
最近写的效率都太低了。大概是因为我只会用递归来解决树的问题。
还有static inline这种要学着用啊。会的东西还是太少了。