資料結構經典遞迴演算法：刪除二元樹所有葉節點

題目需求

編寫遞迴函式，刪除二元樹中所有葉節點 (無左、右子節點的節點)，並正確更新父節點指標。

遞迴邏輯分析

• 基礎案例：節點為 null，直接返回。
• 葉節點判斷：node->left == null && node->right == null。
• 刪除動作：釋放記憶體，並將父節點對應指標設為 null。
• 遞迴下探：非葉節點則遞迴處理左右子樹。

C/C++ 實作 (指標參考傳遞)

// 使用指標的指標 (或引用) 以便修改父節點的 left/right 指標
void deleteLeaves(Node** nodePtr) {
    if (!nodePtr || !*nodePtr) return;
    
    Node* node = *nodePtr;
    
    // 1. 先遞迴處理子樹 (後序遍歷)
    deleteLeaves(&node->left);
    deleteLeaves(&node->right);
    
    // 2. 遞迴返回後，檢查當前節點是否變成葉節點
    // (原本非葉節點，子節點被刪除後可能變成葉節點)
    if (node->left == nullptr && node->right == nullptr) {
        delete node;        // 釋放記憶體
        *nodePtr = nullptr; // 更新父節點指標
    }
}

// 呼叫入口
void deleteAllLeaves(Node*& root) { // C++ 引用更簡潔
    deleteLeaves(&root);
}

Java 實作 (物件參考無法直接修改，需回傳新子樹)

public TreeNode deleteLeaves(TreeNode node) {
    if (node == null) return null;
    
    // 遞迴處理子樹，接收回傳的新子樹根節點
    node.left = deleteLeaves(node.left);
    node.right = deleteLeaves(node.right);
    
    // 刪除當前葉節點：回傳 null 給父節點
    if (node.left == null && node.right == null) {
        return null; // GC 會回收原節點
    }
    return node;
}

// 呼叫
root = deleteLeaves(root);

關鍵細節：後序遍歷的必要性

必須採用後序 (Left-Right-Root)：先處理子樹，再判斷當前節點。因為刪除子葉後，父節點可能新變成葉節點，同一輪遞迴即可處理 (如鏈狀樹)。

複雜度分析

• 時間：O(n) — 每個節點訪問一次。
• 空間：O(h) — 遞迴呼叫堆疊深度，h 為樹高。最壞 O(n) (鏈狀)，平均 O(log n) (平衡樹)。

測試案例

//       1
//      / \
//     2   3
//    /   / \
//   4   5   6
// 輸入上述樹，刪除葉節點 4,5,6 後：
//       1
//      / \
//     2   3
// 再次呼叫 (若需全刪至空) 則刪 2,3 再刪 1。