Remove Node in Binary Search Tree -1.png
Remove Node in Binary Search Tree -2.png
解題思路 ：
首先要先找到想移除的點 利用比較 target 跟當前檢查的 node value 比較 較大就往右子樹找 較小就往左子樹 直到找到為止 一旦找到之後 有三種可能狀況:
- 要移除的點沒有 left child : 如此只要回傳 right child 來連接移除點的 parent
- 要移除的點沒有 right child : 如此只要回傳 left child 來連接移除點的 parent
(如果兩邊都沒有 child 怎麼辦? 那會符合 1, 2 其中一項 回傳另一邊 但是另一邊還是 nullptr 所以回傳值就是 nullptr 等於刪掉此點) - 兩邊都有 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;
}
};
