力扣HOT100之二叉树：108. 将有序数组转换为二叉搜索树

这道题之前做过，思路又给忘了，这道题用递归做是最简单的。
由于得到的数组是有序的，我们只需要取出中间位置的元素medium作为根节点，然后medium左边的剩余元素组成根节点的左子树，medium右边的剩余元素组成根节点的右子树。这里我们需要使用迭代器构造的方式分别构造出左边的子数组和右边的子数组，然后再递归调用sortedArrayToBST()分别将左子树和右子树构造出来，最终将根节点返回即可。

/*** 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* sortedArrayToBST(vector<int>& nums) {//本题用递归来做if(nums.size() < 1)return nullptr;int medium = nums.size() / 2;TreeNode* root = new TreeNode(nums[medium]);  //将中间位置的数值设置为根节点//左边的剩余元素构成左子树vector<int> left_part(nums.begin(), nums.begin() + medium);root -> left = sortedArrayToBST(left_part);//右边的剩余元素构成右子树vector<int> right_part(nums.begin() + medium + 1, nums.end());root -> right = sortedArrayToBST(right_part);return root;}
};