题目描述

给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的结点值。

如果一棵二叉搜索树中，每个结点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的。

如果有多种构造方法，请你返回任意一种。

样例

输入：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 之间。

算法

(中序遍历，暴力重构) $O(n)$

1. 中序遍历原二叉搜索树，将所有结点放到一个数组中。
2. 然后根据这个数组，按照每次二等分的方式递归重构一棵平衡的二叉搜索树

时间复杂度

• 每个结点仅遍历一次，重新生成一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的时间记录中间结果以及存储答案。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void get_nums(TreeNode *root, vector<int> &nums) {
        if (!root) return;
        get_nums(root->left, nums);
        nums.push_back(root->val);
        get_nums(root->right, nums);
    }

    TreeNode* build(int l, int r, const vector<int> &nums) {
        if (l > r) return NULL;

        int mid = (l + r) >> 1;
        TreeNode *rt = new TreeNode(nums[mid]);
        rt->left = build(l, mid - 1, nums);
        rt->right = build(mid + 1, r, nums);
        return rt;
    }

    TreeNode* balanceBST(TreeNode* root) {
        vector<int> nums;
        get_nums(root, nums);

        return build(0, nums.size() - 1, nums);
    }
};