LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 二叉搜索树的中序遍历就是升序排序的，因此题目实际就是根据中序遍历构建二叉搜索树。又因为要保持高度平衡，所以每次取中间元素为根节点，左侧元素为左子树，右侧元素为右子树即可

class Solution {
 public:
  TreeNode* sortedArrayToBST(vector<int>& nums) {
    return dfs(nums, 0, size(nums));
  }

  TreeNode* dfs(vector<int>& nums, int l, int r) {
    if (l >= r) {
      return nullptr;
    }
    int m = l + (r - l) / 2;
    TreeNode* t = new TreeNode(nums[m]);
    t->left = dfs(nums, l, m);
    t->right = dfs(nums, m + 1, r);
    return t;
  }
};