class Solution {
public:
    vector<TreeNode*> inorder;
    void inorderTraversal(TreeNode* root)
    {
        if(root==NULL)return ;
        inorderTraversal(root->left);
        inorder.push_back(root);
        inorderTraversal(root->right);
    }
    TreeNode* build(int l,int r)
    {
        if(l>r)return NULL;
        int mid = l+(r-l)/2;
        TreeNode* root = inorder[mid];
        root->left = build(l,mid-1); 
        root->right = build(mid+1,r);
        return root;
    }
    TreeNode* balanceBST(TreeNode* root) {
        if(root==NULL)return root;
        inorderTraversal(root);
        int n = inorder.size();
        root = build(0,n-1);
        return root;
    }
};