leetcode 1382. 将二叉搜索树变平衡

2023.9.8

       本题分为两步，先用中序遍历将二叉搜索树转化为排序数组，再通过排序数组构建一个平衡二叉树。 代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector<int> v;
    //将排序树转化为排序数组
    void trans(TreeNode* cur)
    {
        if(cur == nullptr) return;
        trans(cur->left);
        v.push_back(cur->val);
        trans(cur->right);
    }
    //将有序数组转化为平衡二叉树
    TreeNode* getTree(vector<int> &nums , int left , int right)
    {
        if(left > right) return nullptr;
        int seg = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[seg]);
        root->left = getTree(nums , left , seg-1);
        root->right = getTree(nums , seg+1 , right);
        return root;
    }
public:
    TreeNode* balanceBST(TreeNode* root) {
        trans(root);
        TreeNode* node = getTree(v,0,v.size()-1);
        return node;
    }
};

         本题的这两个步骤可以当作模板背下来。