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

题目描述

给你一个整数数组 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);}
};

结果