Balance a Binary Search Tree ใน C++ : ทำให้ BST สมดุล (Height-Balanced)

ให้ **Binary Search Tree (BST)** แปลงเป็น **Height-Balanced BST** (ความสูง Left/Right Subtree ของทุก Node ต่างกัน ≤ 1) ค่า Node เหมือนเดิม ถ้าหลายคำตอบ คืนอันไหนก็ได้

ตัวอย่าง

Input BST (Skewed):
1
 \
  2
   \
    3
     \
      4

Balanced BST (หนึ่งรูปแบบ):
      2
     / \
    1   3
         \
          4
(หรือ 3 เป็น Root ก็ได้)

แนวทาง: Inorder Traversal + Build Balanced BST from Sorted Array

1. Inorder Traversal BST -> ได้ **Sorted Array** ของ Values (BST Property)
2. Build Balanced BST จาก Sorted Array แบบ Divide & Conquer:
   • Mid Element -> Root
   • Left Half -> Left Subtree (Recursive)
   • Right Half -> Right Subtree (Recursive)

วิธีนี้รับประกัน Height-Balanced เพราะแบ่งครึ่งทุกครั้ง

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> inorderVals;

    // 1. Inorder traversal to collect sorted values
    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        inorderVals.push_back(node->val);
        inorder(node->right);
    }

    // 2. Build balanced BST from sorted array [l, r]
    TreeNode* build(int l, int r) {
        if (l > r) return NULL;
        int mid = l + (r - l) / 2;
        TreeNode* root = new TreeNode(inorderVals[mid]);
        root->left = build(l, mid - 1);
        root->right = build(mid + 1, r);
        return root;
    }

    TreeNode* balanceBST(TreeNode* root) {
        inorder(root);
        return build(0, inorderVals.size() - 1);
    }
};

Input / Output

Input:  [1,null,2,null,null,null,3,null,null,null,null,null,null,null,4] (Level Order)
Output: [2,1,3,4] (Level Order of one possible balanced BST)

ความซับซ้อน (Complexity)

• Time: O(N) — Inorder O(N) + Build O(N)
• Space: O(N) — Array เก็บ Values + Recursion Stack O(log N)

จุดสำคัญ

• BST Inorder = Sorted Array (Key Property)
• Build from Sorted Array Mid = Root -> Guaranteed Balanced
• ไม่ต้อง Rotation (AVL/Red-Black) วิธีนี้เรียบง่ายกว่าสำหรับ One-time Rebalance

Classic Technique: "Flatten to Array, Rebuild Balanced" ครับ