LeetCode 1382. 将二叉搜索树变平衡（中序遍历+二分递归）

示例
输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
 
提示：
树节点的数目在 1 到 10^4 之间。
树节点的值互不相同，且在 1 到 10^5 之间。

class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        if(!root)
            return root;
        stack<TreeNode*> s;
        vector<TreeNode*> v;
        TreeNode* tp;
        while(root || !s.empty())
        {
            while(root)
            {
                s.push(root);
                root = root->left;
            }
            tp = s.top();
            s.pop();
            root = tp->right;
            tp->left = NULL;
            tp->right = NULL;
            v.push_back(tp);
        }
        return build(v,0,v.size()-1);
    }

    TreeNode* build(vector<TreeNode*>& v, int l, int r)
    {
        if(l > r)
            return NULL;
        int mid = l+((r-l)>>1);
        TreeNode* root = v[mid];
        root->left = build(v,l,mid-1);
        root->right = build(v,mid+1,r);
        return root;
    }
};