伊犁州建设局网站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;}
};