Remove Node in Binary Search Tree -1.png

Remove Node in Binary Search Tree -2.png

解題思路 ：

首先要先找到想移除的點 利用比較 target 跟當前檢查的 node value 比較 較大就往右子樹找 較小就往左子樹 直到找到為止 一旦找到之後 有三種可能狀況:

1. 要移除的點沒有 left child : 如此只要回傳 right child 來連接移除點的 parent
2. 要移除的點沒有 right child : 如此只要回傳 left child 來連接移除點的 parent
   (如果兩邊都沒有 child 怎麼辦? 那會符合 1, 2 其中一項 回傳另一邊 但是另一邊還是 nullptr 所以回傳值就是 nullptr 等於刪掉此點)
3. 兩邊都有 child 則找到右邊子樹的最小數值那點 ( right child 的最左下子孫 ) 把此點的數值跟要刪除的點互換 然後要繼續 recursive 往 right child 跑去把換掉的點殺掉

最後再回傳剛剛換過數值的點( 原本要刪除的點) 即可

C++ code :

<pre><code>
/**

• Definition of TreeNode:
• class TreeNode {
• public:

• int val;
  

• TreeNode *left, *right;
  

• TreeNode(int val) {
  

•     this->val = val;
  

•     this->left = this->right = NULL;
  

• }
  

• }
  */

class Solution {

public:

/**
 * @param root: The root of the binary search tree.
 * @param value: Remove the node with given value.
 * @return: The root of the binary search tree after removal.
 */
 
TreeNode* findMini(TreeNode *root)
{
    TreeNode *tmp = root;
    while(tmp->left)
    {
        tmp = tmp->left;
    }
    return tmp;
}

TreeNode* removeNode(TreeNode* root, int value) {
    // write your code here
    if(root == nullptr) return root;
    if(value > root->val) root->right = removeNode(root->right, value);
    else if(value < root->val) root->left = removeNode(root->left, value);
    else{
        if(!root->left) return root->right;
        if(!root->right) return root->left;
        TreeNode *minNode = findMini(root->right);
        int remove_val = root->val;
        root->val = minNode->val;
        minNode->val = remove_val;
        root->right = removeNode(root->right, value);
    }
    return root;
}

};