力扣每日一题108:将有序数组转换为二叉搜索树

时间:2024-05-10 21:31:59

题目

简单

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 

平衡

 二叉搜索树。

示例 1:

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

示例 2:

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 按 严格递增 顺序排列

面试中遇到过这道题?

1/5

通过次数

471.9K

提交次数

601.7K

通过率

78.4%

思路

平衡二叉搜索树有两个要求

1、每个节点左右子树的高度差不能超过1

2、每个节点的大于所有左子树结点,小于所有右子树结点。

要满足第一个条件的话,我们可以递归建树,每次将中间的值作为根节点,然后递归调用左右两部分。

要满足第二个条件,只需将root->left指向左边部分递归的结果,root->right指向右边部分递归的结果即可。

代码

/**
 * 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 {
public:
    TreeNode *creat(int lo,int hi,vector<int>& nums)
    {
        if(lo>hi) return NULL;
        int mid=(lo+hi)/2;
        TreeNode *root=new TreeNode;
        root->val=nums[mid];
        root->left=creat(lo,mid-1,nums);
        root->right=creat(mid+1,hi,nums);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int lo=0,hi=nums.size()-1;
        TreeNode *root=creat(lo,hi,nums);
        return root;
    }
};