C++ code with comments


  • 0
    G
        // Binary search for the interested node and if it
        // 1. is a leaf node - easy, just delete it
        // 2. only has right subtree - delete it and bring the right subtree to its place
        // 3. only has left subtree - delete it and bring the left subtree to its place
        // 4. has both subtrees - find the min node in the right subtree, swap it with this node and call deleteNode() again
        TreeNode* deleteNode(TreeNode* root, int key) {
            if (!root) {
            } else if (key < root->val) {
                root->left = deleteNode(root->left, key);
            } else if (key > root->val) {
                root->right = deleteNode(root->right, key);
            } else {
                if (!root->left) {
                    return root->right;
                } else if (!root->right) {
                    return root->left;
                } else {
                    root->val = getMin(root->right);
                    root->right = deleteNode(root->right, root->val);
                }
            }
            return root;
        }
        int getMin(TreeNode* root) {
            int ret = 0;
            while (root) {
                ret = root->val;
                root = root->left;
            }
            return ret;
        }
    

Log in to reply
 

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