链接
https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
耗时
解题:20 min
题解:14 min
题意
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
思路
递归解决。
根节点的值应该是有序数组正中间的数,这样左右子树才能平衡。根节点的左子树就是数组最左边到中间,右子树是中间到最右边。同样的左子树的根节点的值应该是数组最左边到中间这段区间正中间的值,右子树同理。依此类推下去,直到子树所对应的数组区间中不存在元素为止。
时间复杂度:
O
(
n
)
O(n)
O(n)
AC代码
class Solution {
public:
void solve(vector<int>& nums, int l, int r, TreeNode*& root) {
if(l >= r) return ;
int m = l + ((r-l)>>1);
root = new TreeNode;
root->val = nums[m];
solve(nums, l, m, root->left);
solve(nums, m+1, r, root->right);
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
int n = nums.size();
if(n == 0) return NULL;
TreeNode* root;
solve(nums, 0, n, root);
return root;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)