题目详情：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
解题思路：
这道题初看不知道如何写代码。仔细想想发现了二叉树一直都有的套路：二叉树相关--->二叉树遍历--->递归。
这题要求根据数组构建二叉树，那就构吧。初步是这样想的：
1、从数组里选一个元素构建新的根节点
2、从数组里选两个元素作为上述节点的左右孩子节点
3、遍历完整个数组为止。
step1：该如何选择节点作为根节点？
题目中提到了要求构建的二叉树是高度平衡的二叉树，而题目给出的数组是升序。那如果我取数组nums[start,end]的中间nums[mid]元素作为根节点，左右两边的元素数量差最多是1。刚好可以满足题目要求的高度平衡。
step2：该如何选择根节点的左右孩子节点？
选取的nums[mid]把数组分成了左右两个部分，把左右两个部分单独处理，即
左边范围是[0，mid-1]，右边范围是[mid+1，nums.length-1]
假设题目给的数组范围是[0，mid-1]，选取的根节点步骤是和step1一模一样，只是数组大小不同而已。
因此在左边范围一样取中间元素作为step1中根节点的左孩子，右边范围取中间元素作为step1中根节点的右孩子
step3：啥时候停止？
因为需要不断更新使用数组的范围，确保节点的构建，所以start会增加而end会减少，当start>end时，就停止生成节点，也就是停止递归。
结合代码看，更好理解
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { if(nums.size()==0) return nullptr; return helper(nums,0,nums.size()-1); } TreeNode* helper(vector<int>& nums,int start,int end){ //递归结束 if(start>end){ return nullptr; } //取中间元素 int midIndex=start+(end-start)/2; int CurNum=nums[midIndex]; TreeNode* node=new TreeNode(CurNum);//构建根节点 //左孩子 node->left=helper(nums,start,midIndex-1);//更新数组使用范围 //右孩子 node->right=helper(nums,midIndex+1,end);//更新数组使用范围 return node; } };
根据这道题，可以关联到其他题，解法是一样的，如下图所示
