自我修炼_初级算法篇_leetcode_第30题_leetcode第30题

将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

 

 

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。

 

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xninbt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个题应该是数据结构里考过的一类题，平衡二叉树（AVL）。按照中序遍历的方法。我们可以得到左根右排列的数组。这样我们就可以辨别出他是否 是平衡的。也就是左边的值<根值<右边的值。我们拿实例1为例子。他的数组形式应该是[-10,-3,null,0,5,9,null];

如何选取根节点，我们知道中序遍历的根节点是中间的点。也就是我们的（数组长度-1）/2.

选好根节点如何显示出其左子树和左子树的根节点。

这样我们就需要用到递归的代码

所以现在我们的递归出口是什么，是否就是数组长度小于等于0的情况。我们相当于先筛查这个栗子中根节点的左半边在筛查右半边，如果左半边他还有子节点我们在递归的筛查对吧。

首先是递归出口，我们的函数的实参使用了类似于双指针的方法记录了要比较的范围。

所以递归出口如下。

 TreeNode* paixu(vector<int>& nums,int left,int right){
         if (left > right) {
            return nullptr;
        }
}

接下来就是让他左边的递归paixu，右边的也递归paixu

 
        int mid = (left + right) / 2;
 
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = paixu(nums, left, mid - 1);
        root->right = paixu(nums, mid + 1, right);
        return root;