450. Delete Node in a BST

題目網址：https://leetcode.cn/problems/delete-node-in-a-bst/

題意：給一 BST 的 root 和一個值 key, 刪除 BST 中的 key 對應的 node, 並保證 BST 的性質不變。返回刪除後 BST 的 root。

一般來說，刪除 node 可分為兩個步驟：

• 首先找到需要刪除的 node
• 如果找到了, 則刪除它

Solution：

想法：利用 DFS

• 若 key > root->val, 則去右子樹中刪除
• 若 key < root->val, 則去左子樹中刪除
• 若 key == root->val, 則分為以下三種情況：

  • 若 root 無左子, 則 root 的右子頂替其位置

  • 若 root 無右子, 則 root 的左子頂替其的位置

  • 若 root 左右子都有, 則將其左子樹轉移到其右子樹的最左 node (也就是右子樹中最小的 node) 的左子樹上, 然後 root 的右子樹頂替其位置

    

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) {
            return root;
        }

        if (key > root->val) {
            root->right = deleteNode(root->right, key);
        } else if (key < root->val) {
            root->left = deleteNode(root->left, key);
        } else {
            if (!root->left) { // 無左子
                return root->right;
            }

            if (!root->right) { // 無右子
                return root->left;
            }

            // 到右子中找到最小的 node
            // 最小的 node 其左子必為空, 不然它不會是右子中最小的 node
            TreeNode *node = root->right;
            while (node->left) {
                node = node->left;
            }

            node->left = root->left; // 把 root->left 成為右子樹中最小的 node 之左子
            root = root->right; // root 的右子樹頂替其位置
        }

        return root;
    }
};

• time：$O(h)$ ➔ 最多拜訪 h 個 node
• space：$O(h)$ ➔ 取決於遞迴深度, 遞迴深度不超過樹高 h