【代码随想录day 20】 力扣 108.将有序数组转换为二叉搜索树

视频讲解：https://www.bilibili.com/video/BV1uR4y1X7qL/?share_source=copy_web&vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E6%80%9D%E8%B7%AF
力扣题目：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

这道题可以偷懒将二叉树写成一条队列形式，但是没必要，主要思路如下：

1. 找到数组中心值作为root根节点，左边作为左子树，右边作为右子树。
2. 进入递归部分，每次选中中心作为根节点，当左范围大于右范围递归终止。
3. 最后返回整棵树。

class Solution {
public:TreeNode *travesal(vector<int>&nums, int left, int right){//判断终止条件if(left > right) return NULL;int mid = (left + right)/2;TreeNode *root= new TreeNode(nums[mid]);//递归root->left = travesal(nums, left, mid-1);root->right = travesal(nums, mid+1, right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {TreeNode *result = travesal(nums, 0, nums.size()-1);return result;}
};