Very Concise Recursive C++ Solution


  • 0

    We will only do deletion when root->val == NULL, so if root->val > key we can know that the key is in the left subtree, then root->left = deleteNode(root->left, key), if root->val < key should do root->right = deleteNode(root->right, key).

    When root->val == NULL we need to delete root. If root->left == NULL && root->right == NULL we can just delete root and return NULL, else we can chose root->left or root->right to be the new root in case it is not NULL.

    class Solution 
    {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) 
        {
        	if(root == NULL) return NULL;
    
            if(root->val == key)
            {
            	if(root->right)
            	{
            		TreeNode* p = root->right;
            		while(p->left) p = p->left;
            		p->left = root->left;
            		return root->right;
            	}
            	else if(root->left)
            		return root->left;
            	else return NULL;
            }
    
            if(root->val > key)
            	root->left = deleteNode(root->left, key);
            if(root->val < key)
            	root->right = deleteNode(root->right, key);
    
            return root;
        }
    };
    

Log in to reply
 

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