題目： LeetCode - 450. Delete Node in a BST

題目說明

給一個 Binary Search Tree，和一個整數 key，如果找到 key 的節點就將其刪除。

解題思路

由於 BST 有左子樹的值皆比根的值小，右子樹的值皆比根的值大的特性，所以我們先判斷當前 node 的值及 key 的大小，若 key 較大則往左邊走，否則往右邊走。若兩者的值相等代表要刪除當前的 node，若是當前的 node 只有一邊的子樹，那就直接接上即可，否則要從右子樹中找出最小的值頂替目前的 node 才能符合 BST 的特性。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root) return root;
        if(root->val < key) root->right = deleteNode(root->right, key);
        else if(root->val > key) root->left = deleteNode(root->left, key);
        else // root->val == key
        {
            if(!root->left || !root->right)
            {
                auto newRoot = root->right ? root->right : root->left;
                delete root;
                return newRoot;
            }
            else
            {
                auto min = root->right;
                while(min->left) min = min->left;
                root->val = min->val;
                root->right = deleteNode(root->right, min->val);
            }
        }
        return root;
    }
};