108 将有序数组转换为二叉搜索树
给定中序遍历结果求二叉搜索树,结果不一定唯一
给定中序遍历结果求平衡的二叉搜索树,结果不一定唯一
因此,题目给出了多种可能的答案,表示都可以
思路:
- 二叉搜索树的中序遍历是递增数组
- 我们每次取二叉搜索树的中间值,这个值就是根节点
- 根节点左边是它的左子树,右边是它的右子树
- 接着重复步骤2和步骤3,即可获得二叉搜索树
有个小坑:
如何证明以上做法能够保证二叉搜索树是平衡的
证明见以下链接
https://leetcode.cn/problems/balance-a-binary-search-tree/solutions/241897/jiang-er-cha-sou-suo-shu-bian-ping-heng-by-leetcod/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
TreeNode* dfs(vector<int>& nums, int start, int end){
if(start > end)
return nullptr;
int mid = (start + end) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = dfs(nums, start, mid - 1);
root->right = dfs(nums, mid + 1, end);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return dfs(nums, 0 ,nums.size() - 1);
}
};
复杂度分析
时间复杂度:O(n),其中 n 是数组的长度。每个数字只访问一次。
空间复杂度:O(logn),其中 n 是数组的长度。空间复杂度不考虑返回值,因此空间复杂度主要取决于递归栈的深度,递归栈的深度是 O(logn)。