Given a root of Binary Search Tree with unique value for each node. Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.
Example
Analysis:
Given binary search tree:
5
/ \
3 6
/ \
2 4
Remove 3, you can either return:
5
/ \
2 6
\
4
or :
5
/ \
4 6
/
2
The logic is simple:
1) find the node with the given value;
2) if left subtree is NULL, return the right subtree
3) if right subtree is NULL, return the left subtree
4) find and delete the maximum node in the left subtree, and replace value( If we want to actually delete the node, that will be more complicated.)
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
if (root->val == key) {
if (!root->right) {
TreeNode* left = root->left;
delete root;
return left;
}
else {
TreeNode* right = root->right;
while (right->left)
right = right->left;
swap(root->val, right->val);
}
}
root->left = deleteNode(root->left, key);
root->right = deleteNode(root->right, key);
return root;
}
};
