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

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

class Solution {
  TreeNode *Dispatch(vector<int> &V, int L, int R) {
    if (L == R)
      return {};
    int M = (L + R) / 2;
    TreeNode *Root = new TreeNode(V[M], Dispatch(V, L, M),
                                  Dispatch(V, M + 1, R));
    return Root;
  }
public:
  TreeNode* sortedArrayToBST(vector<int>& nums) {
    return Dispatch(nums, 0, nums.size());
  }
};

这题其实是一个二分问题。对数组进行二分之后左右元素数量的最大差值是不超过 1 的，顶多就是一奇一偶，所以构造出来的树自然也就是平衡的。

二刷

class Solution {
  TreeNode *Build(vector<int> &nums, int L, int R) {
    if (L == R)
      return nullptr;

    int M = L + (R - L) / 2;
    TreeNode *TN = new TreeNode(nums[M]);
    TN->left = Build(nums, L, M);
    TN->right = Build(nums, M + 1, R);
    return TN;
  }
public:
  TreeNode* sortedArrayToBST(vector<int>& nums) {
    return Build(nums, 0, nums.size());
  }
};

跟一刷差不多，思路非常清晰。