题目描述

在这里插入图片描述

原题链接：108. 将有序数组转换为二叉搜索树

解题思路

为了构建平衡二叉搜索树，可采用二分的方式，构建一个二分查找搜索树。因此，本题的关键就在于切割点，划分出左右区间，然后继续向下进行切割。思路类似于 106. 从中序与后序遍历序列构造二叉树（递归法），因为传入的是有序数组，因此本题的切割点时有序数组的中间值，左侧为左区间，右侧右区间。

/*** 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) {        int n = nums.size();if(n == 0)        return NULL;TreeNode* root;if(n == 1) {        // vector只剩一个数时，返回这个数root = new TreeNode(nums[0]);            } else {root = new TreeNode(nums[n / 2]);                               // 取中间结点作为根节点vector<int> leftnums(nums.begin(), nums.begin() + n / 2);       // 切割左区间遍历vector<int> rightnums(nums.begin() + n / 2 + 1, nums.end());    // 切割区间遍历root->left = sortedArrayToBST(leftnums);root->right = sortedArrayToBST(rightnums);}                return root;}
};