跳转至

108 将有序数组转换为二叉搜索树

给定中序遍历结果求二叉搜索树,结果不一定唯一

给定中序遍历结果求平衡的二叉搜索树,结果不一定唯一

因此,题目给出了多种可能的答案,表示都可以

思路:

  1. 二叉搜索树的中序遍历是递增数组
  2. 我们每次取二叉搜索树的中间值,这个值就是根节点
  3. 根节点左边是它的左子树,右边是它的右子树
  4. 接着重复步骤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)。