C++ 32ms solution with explanation


  • 0
    D

    Three are basically two situations for the key node which is being deleted.

    1. The key node has at least one NULL child.
    2. The key node has two NOT NULL children.

    For situation 1) let the parent node point to NULL (if both of the children are NULL), or point to the NOT NULL child, and then delete the key node.
    For situation 2) replace the key node value with the smallest value which is bigger than the key or the biggest value which is smaller than the key in the BST, and then delete the node which holds the replaced value. The deletion is handled as situation 1) since the node being deleted guarantees one NULL child.
    The smallest value which is bigger than the key is the most left leaf in the right child tree of the key node, and the smallest value which is bigger than the key is the most right leaf in the left child tree of the key node. These are the two valid answers shown in the problem example. In the code here, the smallest value which is bigger than the key is used.

    class Solution {
    private:
        // function to delete key node 
        // if it has at least one NULL child
        void deleteKeyNode(TreeNode* preKeyNode, TreeNode* keyNode) {
            if (keyNode == NULL) return;
            if ((keyNode->left == NULL) && (keyNode->right == NULL)) {
                if (preKeyNode->left == keyNode) 
                    preKeyNode->left = NULL; 
                else preKeyNode->right = NULL;
                delete keyNode;
            }
            else if (keyNode->left == NULL) {
                if (preKeyNode->left == keyNode) 
                    preKeyNode->left = keyNode->right;
                else preKeyNode->right = keyNode->right;
                delete keyNode;
            }
            else if (keyNode->right == NULL) {
                if (preKeyNode->left == keyNode) 
                    preKeyNode->left = keyNode->left;
                else preKeyNode->right = keyNode->left;
                delete keyNode;
            }
        }
        
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            TreeNode* cur = root;
            TreeNode dummy = TreeNode(-1);
            TreeNode* pre = &dummy; 
            pre->left = root;
            while(cur && cur->val != key) { // try to find key
                pre = cur;
                if (key < cur->val) cur = cur->left; 
                else cur = cur->right;   
            }
            if (cur == NULL) return dummy.left; // cannot find key
            TreeNode* holdCur = cur;
            // situation 1)
            // delete key node if it has at least one NULL child
            deleteKeyNode(pre,cur); 
            
            // situation 2)
            // if keyNode has two children
            if (holdCur == cur && cur->left && cur->right) {
                pre = cur; cur = cur->right;
                // find the smallest value which is bigger than key
                while (cur->left) { 
                    pre = cur;
                    cur = cur->left;
                }
            holdCur->val = cur->val; // replace key node value 
            // delete the node which holds the replaced value
            deleteKeyNode(pre,cur); 
            
            return dummy.left;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.