C++ 算法：判斷平衡二叉樹與求二叉樹鏡像（遞歸與優化）

1. 判斷平衡二叉樹

定義：任意節點左右子樹高度差 ≤ 1。

方法一：自頂向下（重複遍歷，O(n²)）

int depth(TreeNode* root) {
    if (!root) return 0;
    return max(depth(root->left), depth(root->right)) + 1;
}
bool isBalanced(TreeNode* root) {
    if (!root) return true;
    int ld = depth(root->left), rd = depth(root->right);
    return abs(ld - rd) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}

缺點：每個節點重複計算子樹高度。

方法二：自底向上（後序遍歷，O(n)）

遞歸返回 (是否平衡, 高度)。若子樹不平衡直接向上傳遞 false。

pair check(TreeNode* root) {
    if (!root) return {true, 0};
    auto [lbal, lh] = check(root->left);
    auto [rbal, rh] = check(root->right);
    if (!lbal || !rbal || abs(lh - rh) > 1) return {false, 0};
    return {true, max(lh, rh) + 1};
}
bool isBalanced(TreeNode* root) { return check(root).first; }

2. 求二叉樹鏡像

交換每個節點的左右子樹。

方法一：前序遍歷（先交換再遞歸）

void mirror(TreeNode* root) {
    if (!root) return;
    swap(root->left, root->right);
    mirror(root->left);
    mirror(root->right);
}

方法二：後序遍歷（先遞歸再交換，返回新根）

TreeNode* mirror2(TreeNode* root) {
    if (!root) return nullptr;
    TreeNode* l = mirror2(root->left);
    TreeNode* r = mirror2(root->right);
    root->left = r; root->right = l;
    return root;
}

完整測試代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val; TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
// 插入構建 BST（僅為測試）
void insert(TreeNode*& root, int v) {
    if (!root) { root = new TreeNode(v); return; }
    if (v < root->val) insert(root->left, v);
    else if (v > root->val) insert(root->right, v);
}
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << ' ';
    preorder(root->left);
    preorder(root->right);
}
int main() {
    TreeNode* root = nullptr;
    for (int v : {9,3,6,1,2,5,8,7,10}) insert(root, v);
    cout << "Original: "; preorder(root); cout << '\n';
    mirror(root);
    cout << "Mirrored: "; preorder(root); cout << '\n';
    cout << "Balanced: " << isBalanced(root) << '\n';
    return 0;
}

複雜度

• 平衡判斷優化版：O(n) 時間，O(h) 空間（遞歸棧）。
• 鏡像：O(n) 時間，O(h) 空間。

關鍵點

• 平衡樹判斷必須自底向上，避免重複計算高度。
• 鏡像操作本質是左右子樹遞歸交換，前序/後序均可。
• C++17 結構化綁定 (`auto [a,b] = ...`) 簡化 pair 返回值處理。

這兩題是二叉樹遞歸的基礎練習，掌握「返回多值信息」與「遍歷順序選擇」是關鍵。