将有序数组转换为二叉搜索树

题面

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

示例 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,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

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

分析

• 从中间将数组分为两半，然后递归构造左右子树即可，代码如下

  /**
   * 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* range(vector<int>& nums, int l, int r) {
          if (l == r) {
              return new TreeNode(nums[l]);
          }
          if (l + 1 == r) {
              return new TreeNode(nums[r], new TreeNode(nums[l]), nullptr);
          }
          int mid = l + (r - l) / 2;
          TreeNode* left = range(nums, l, mid - 1);
          TreeNode* right = range(nums, mid + 1, r);
          return new TreeNode(nums[mid], left, right);
      }
      TreeNode* sortedArrayToBST(vector<int>& nums) {
          return range(nums, 0, nums.size() - 1);
      }
  };