🔗 🟡 1382. Balance a Binary Search Tree 1541

tags: `Weekly Contest 180` `DFS` `樹(Tree)` `二元樹(Binary Tree)` `BST` `分治法(Divide and Conquer)` `貪心(Greedy)`

題意

給定一個 二元搜尋樹(Binary Search Tree, BST) 的根節點 $root$ ，請將其轉換為一個平衡的二元搜尋樹，新生成的樹應該與原來的樹有着相同的節點值。如果有多種構造方法，請你返回任意一種。

如果一棵二元搜尋樹中，每個節點的兩棵子樹高度差不超過 $1$ ，我們就稱這棵二元搜尋樹是 平衡的 。

思路：中序遍歷 + 分治法

雖然看似需要用 AVL 樹或紅黑樹等平衡二元搜尋樹的 旋轉(Rotation) 來解決，但其實只需要基於貪心(Greedy) 的思路，使得左右子樹的節點數量盡量平均，進而達到平衡的效果。

為了利用及維持二元搜尋樹的性質，我們可以先對其進行中序遍歷，將節點值存儲在一個列表 $nums$ 中，使得 $nums$ 是一個有序列表。

然後根據 $nums$ 中間值建立一個新的平衡二元搜尋樹，選擇 $nums$ 中間的元素作為新的根節點，然後遞迴地構建左右子樹。因為每次都選擇中間元素作為根節點，所以新生成的二元搜尋樹一定是平衡的。在遞迴過程中會不斷的把問題分解成兩個子問題，直到到達邊界條件為止，這裡利用到了分治法(Divide and Conquer) 的思想。

令 $[l, r]$ 表示當前需要構建平衡二元搜尋樹的區間，則中間元素的索引為 $mid = \lfloor \frac{(l + r)}{2} \rfloor$ ，新的根節點的值為 $nums[mid]$ 。然後遞迴地構建左右子樹，左子樹的區間為 $[l, mid - 1]$ ，右子樹的區間為 $[mid + 1, r]$ ，直到區間為空，即 $l > r$ 時返回 $None$ 。遞迴入口為 $[0, n - 1]$ ，其中 $n$ 是 $nums$ 的長度。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $N$ 是原始二元搜尋樹的節點數。我們需要先進行一次中序遍歷將所有節點值保存在 $nums$ 列表中，這需要 $\mathcal{O}(n)$ 的時間。然後我們需要遞迴地構建新的平衡二元搜尋樹，這也需要 $\mathcal{O}(n)$ 的時間。
空間複雜度： $\mathcal{O}(n)$ ，我們需要額外使用 $\mathcal{O}(n)$ 的空間來保存 $nums$ 列表。

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        nums = []
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            nums.append(node.val)
            inorder(node.right)
        def build(l, r):
            if l > r:
                return None
            mid = (l + r) // 2
            node = TreeNode(nums[mid])
            node.left = build(l, mid - 1)
            node.right = build(mid + 1, r)
            return node
        inorder(root)
        return build(0, len(nums) - 1)

class Solution {
public:
    vector<int> nums;
    TreeNode* balanceBST(TreeNode* root) {
        inorder(root);
        return build(0, nums.size()-1);
    }
    void inorder(TreeNode* node) {
        if (node == nullptr) return;
        inorder(node->left);
        nums.push_back(node->val);
        inorder(node->right);
        return;
    }
    TreeNode* build(int l, int r) {
        if (l > r) return nullptr;
        int mid = (l + r) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = build(l, mid - 1);
        node->right = build(mid + 1, r);
        return node;
    }
};