Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.6 kB
1
Indexable
Never
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
TreeNode* deleteNode(TreeNode *root, int number){
    //traversalNode-> to search the value
    //parentNode -> parentNode of traversalNode
    TreeNode *traversalNode = root, *parentNode = NULL;
    while(traversalNode){
        if(traversalNode->val == number){
            break;
        }
        parentNode = traversalNode;
        if(traversalNode->val < number){
            traversalNode = traversalNode->right;
        }
        else{
            traversalNode = traversalNode->left;
        }
    }
    if(traversalNode == NULL){
        return root;
    }
    if(traversalNode->left == NULL && traversalNode->right == NULL){
        if(parentNode == NULL){
            return NULL;
        }
        if(parentNode->left == traversalNode){
            parentNode->left = NULL;
        }
        else{
            parentNode->right = NULL;
        }
        return root;
        //return parentNode->right;
        //delete traversalNode;
    }
    else if(traversalNode->left == NULL){
        if(parentNode == NULL){
            root = root->right;
            return root;
        }
        if(parentNode->left == traversalNode){
            parentNode->left = traversalNode->right;
            //delete traversalNode;
        }
        else{
            parentNode->right = traversalNode->right;
            //delete traversalNode;
        }
    }
    else if(traversalNode->right == NULL){
        if(parentNode == NULL){
            root = root->left;
            return root;
        }
        if(parentNode->right == traversalNode){
            parentNode->right = traversalNode->left;
            //delete traversalNode;
        }
        else{
            parentNode->left = traversalNode->left;
            // delete traversalNode;
        }
    }
    else{
        TreeNode *leftMaxNode = traversalNode->left;
        while(leftMaxNode->right != NULL){
            leftMaxNode = leftMaxNode->right;
        }
        root = deleteNode(root, leftMaxNode->val);
        leftMaxNode->left = traversalNode->left;
        leftMaxNode->right = traversalNode->right;
        if(parentNode == NULL){
            return leftMaxNode;
        }
        if(parentNode->right == traversalNode){
            parentNode->right = leftMaxNode;
        }
        else{
            parentNode->left = leftMaxNode;
        }
    }
    delete traversalNode;
    return root;
}

TreeNode* Solution::solve(TreeNode* A, int B) {
    return deleteNode(A, B);
}