Balance a Binary Search Tree LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> nums;
4
  void traverse(TreeNode *root) {
5
    if (!root) return;
6
    traverse(root->left);
7
    nums.push_back(root->val);
8
    traverse(root->right);
9
    return;
10
  }
11

12
  TreeNode *makeTree(int s, int e) {
13
    if (s > e) return nullptr;
14
    int m = (s + e) / 2;
15
    TreeNode *root = new TreeNode(nums[m]);
16

17
    root->left = makeTree(s, m - 1);
18
    root->right = makeTree(m + 1, e);
19

20
    return root;
21
  }
22

23
  TreeNode *balanceBST(TreeNode *root) {
24
    traverse(root);
25
    return makeTree(0, size(nums) - 1);
26
  }
27
};