二元查找樹鏡像轉換：遞歸與迭代雙重實現

問題定義

輸入一棵二元查找樹（BST），將其轉換為鏡像樹。鏡像定義：原左子樹所有節點值 > 原右子樹所有節點值。例如：

原樹:        8              鏡像:        8
           /   \                    /   \
          6    10                 10    6
         / \  / \                 / \  / \
        5  7 9  11               11 9 7  5

節點結構

struct BSTreeNode {
    int value;
    BSTreeNode *left;
    BSTreeNode *right;
};

解法一：遞歸 —— 簡潔直觀

核心邏輯：交換當前節點左右子指針，遞歸處理左右子樹。

BSTreeNode* Mirror_Solution1(BSTreeNode* pRoot)
{
    if (pRoot != nullptr) {
        BSTreeNode* pRight = pRoot->right;
        BSTreeNode* pLeft  = pRoot->left;
        pRoot->left  = Mirror_Solution1(pRight); // 原右變左
        pRoot->right = Mirror_Solution1(pLeft);  // 原左變右
    }
    return pRoot;
}

複雜度：時間 O(n)，空間 O(h)（h 為樹高，最壞 O(n)）。

解法二：迭代 + 顯式棧 —— 避免棧溢出

利用棧模擬遞歸，層序或前序均可。此處採用前序（根→右→左）配合棧：

BSTreeNode* Mirror_Solution2(BSTreeNode* pRoot)
{
    if (pRoot == nullptr) return nullptr;

    std::stack<BSTreeNode*> stk;
    stk.push(pRoot);

    while (!stk.empty()) {
        BSTreeNode* pNode = stk.top(); stk.pop();

        // 交換左右子女
        BSTreeNode* pLeft  = pNode->left;
        BSTreeNode* pRight = pNode->right;
        pNode->left  = pRight;
        pNode->right = pLeft;

        // 先壓右再壓左，保證前序處理順序（非必需，僅為邏輯對稱）
        if (pLeft)  stk.push(pLeft);
        if (pRight) stk.push(pRight);
    }
    return pRoot;
}

複雜度：時間 O(n)，空間 O(n)（最壞情況棧存所有節點）。

本質對比與選擇建議

建議：平衡樹/深度可控場景首選遞歸；通用庫、深度未知或嵌入式環境用迭代。

擴展：通用二叉樹同理

本算法不依賴 BST 有序性，對任意二叉樹同樣適用。若需保留原樹，可在遞歸/迭代中創建新節點構建鏡像樹。