delete-node-in-a-bst
阅读原文时间:2024年06月10日阅读:1

https://leetcode.com/problems/delete-node-in-a-bst/

/**
* 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 == NULL) {
return NULL;
}

    TreeNode\* cur = root;  
    TreeNode\* last = NULL;  
    while (cur != NULL && cur->val != key) {  
        if (cur->val > key) {  
            last = cur;  
            cur = cur->left;  
        }  
        else {  
            last = cur;  
            cur = cur->right;  
        }  
    }

    if (cur == NULL) {  
        return root;  
    }

    TreeNode\* tlast = cur;  
    TreeNode\* tcur;  
    if (cur->left != NULL) {  
        tcur = cur->left;  
        while (tcur->right != NULL) {  
            tlast = tcur;  
            tcur = tcur->right;  
        }

        if (tcur == tlast->left) {  
            tlast->left = tcur->left;  
        }  
        else {  
            tlast->right = tcur->left;  
        }  
        cur->val = tcur->val;  
    }  
    else if (cur->right != NULL) {  
        tcur = cur->right;  
        while (tcur->left != NULL) {  
            tlast = tcur;  
            tcur = tcur->left;  
        }  
        if (tcur == tlast->left) {  
            tlast->left = tcur->right;  
        }  
        else {  
            tlast->right = tcur->right;  
        }  
        cur->val = tcur->val;  
    }  
    else {  
        if (last == NULL) {  
            // only root  
            return NULL;  
        }  
        if (cur == last->left) {  
            last->left = NULL;  
        }  
        else if (cur == last->right){  
            last->right = NULL;  
        }  
        else {  
            // error  
        }  
    }  
    return root;  
}  

};

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章