C++ solution


  • 0
    R
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            if(!root) return NULL;
            if(key < root->val) {
                root->left = deleteNode(root->left, key);
            }
            else if(key > root->val) {
                root->right = deleteNode(root->right, key);
            }
            else {
                //single or no child case
                if(!root->left || !root->right) {
                    TreeNode* next = root->left ? root->left : root->right;
                    delete root;
                    return next;
                }
                //two children case
                TreeNode* curr = root->right;
                while(curr->left) curr = curr->left;
                root->val = curr->val;
                root->right = deleteNode(root->right, curr->val); //delete curr node
            }
            return root;
        }
    };
    

  • 0
    R

    I wrote the two children case in this way, can you tell me why is it slower than you code?

    //two children case
                TreeNode* curr = root->right,*p = root;
                while(curr->left) {
                    p=curr;
                    curr = curr->left;
                }
                root->val = curr->val;
                if(p->left==curr) p->left=curr->right;
                else p->right=curr->right;
                delete curr;
    

Log in to reply
 

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