- Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
- Basically, the deletion can be divided into two stages:
- Search for a node to remove.
If the node is found, delete the node.
- Note: Time complexity should be O(height of tree).
- Example:
- root = [5,3,6,2,4,null,7]
- key = 3
- 5
- / 3 6
- / \ 2 4 7
- Given key to delete is 3. So we find the node with value 3 and delete it.
- One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
- 5
- / 4 6
- / 2 7
- Another valid answer is [5,2,6,null,4,null,7].
- 5
- / 2 6
- \ 4 7
- class Solution {
- public:
- TreeNode* deleteNode(TreeNode* root, int key) {
- if(!root) return root;
- TreeNode* ret;
- if(root->val == key) {
- TreeNode* rnode_lmost = getlm_or_rm_node(root->right, true);
- if(rnode_lmost) {
- rnode_lmost->left = root->left;
- ret = root->right;
- }else ret = root->left;
- }else {
- if(key <root->val) root->left = deleteNode(root->left, key);
- else root->right = deleteNode(root->right, key);
- ret = root;
- }
- return ret;
- }
- TreeNode* getlm_or_rm_node(TreeNode* root, bool left){
- if(!root) return root;
- if(left) {
- while(root->left) root = root->left;
- }else {
- while(root->right) root = root->right;
- }
- return root;
- }
- };
- class Solution {
- public:
- TreeNode *deleteNode(TreeNode *root, int key) {
- TreeNode **cur = &root;
- while (*cur && (*cur)->val != key)
- cur = (key> (*cur)->val) ? &(*cur)->right : &(*cur)->left;
- if (*cur) {
- if (!(*cur)->right) *cur = (*cur)->left;
- else {
- TreeNode **successor = &(*cur)->right;
- while ((*successor)->left) successor = &(*successor)->left;
- swap((*cur)->val, (*successor)->val);
- *successor = (*successor)->right ? (*successor)->right : nullptr;
- }
- }
- return root;
- }
- };
来源: http://www.bubuko.com/infodetail-2946470.html