5179. 将二叉搜索树变平衡


图片说明


中序序列是有序的，可以二分建平衡树。

class Solution {
public:
    int n=0,a[10004];
    void dfs(TreeNode* root){
        if(root==NULL)return;
        dfs(root->left);
        a[++n]=root->val;
        dfs(root->right);
    }
    TreeNode* tree(int l,int r){
        if(l>r)return NULL;
        int mid=l+r>>1;
        TreeNode* node=new TreeNode(a[mid]);
        node->left=tree(l,mid-1);
        node->right=tree(mid+1,r);
        return node;
    }
    TreeNode* balanceBST(TreeNode* root) {
        if(root==NULL)return root;
        dfs(root);
        return tree(1,n);
    }
};