1382. 將二叉搜索樹變平衡

思路

先把二分搜尋樹轉換為數組，隨後再轉回二分搜尋樹。
在走訪時順序由小到大，因此不需要在那之後排序數組
只要將數組砍半，左邊給左樹，右邊給右樹，就必定是平衡二叉樹。

程式碼

走訪 + 重建

class Solution {
private:
    void traverse(TreeNode* node, vector<int>& nums) {
        // 一邊走訪節點，一邊加入數字。
        if(!node) return;
        traverse(node->left, nums); // 加入左邊，比較小的數字
        nums.push_back(node->val);
        traverse(node->right, nums); // 加入右邊，比較大的數字
    }
    TreeNode* build(vector<int>& nums, int left, int right) {
        if(left > right) return nullptr; // left, right 閉區間。
        int mid = left + (right - left) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = build(nums, left, mid - 1);
        node->right = build(nums, mid + 1, right);
        return node;
    }
public:
    TreeNode* balanceBST(TreeNode* root) {
        vector<int> nums;
        traverse(root, nums);
        TreeNode* res = build(nums, 0, nums.size() - 1);
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$，每個節點走訪兩次
• 空間複雜度：$O(n)$，數組存放排序後的數字。