日照百达建设咨询有限公司内部网站现在有哪些推广平台
文章目录
- 题目描述
- 思路
- 解答（c++）
- 结果
题目描述
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
思路
设置头尾指针，将中间值设置root，然后左右两边进行相同的设置，实现一个递归函数，直到头指针位置大于尾指针位置。
解答（c++）
class Solution {
public:TreeNode* myBuild(vector<int>& nums, int begin, int end){if(begin > end) return nullptr;int mid = begin + (end-begin)/2;TreeNode* root = new TreeNode(nums[mid]);root->left = myBuild(nums, begin, mid-1);root->right = myBuild(nums, mid+1, end);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return myBuild(nums, 0, nums.size()-1);}
};
结果
