Leetcode 450. 删除二叉搜索树中的节点 [二叉搜索树]

题目

思路

如果要删除节点的值大于当前根节点，则向右子树递归删除；如果要删除节点的值小于当前根节点，则向左子树递归删除；如果当前节点就是要删除的节点，则需要考虑当前根节点的值被哪个值所替换:

1. 如果右子树不为空，则将右子树中最小的值赋给当前根节点；
2. 如果右子树为空，但左子树不为空，则将左子树中最大的值赋给当前节点；
3. 如果左右子树均为空，则将当前节点置为空即可

代码

class Solution {
    
public:
        TreeNode* deleteNode(TreeNode* root, int key) {
    
            if(root == nullptr) return root;
            else if(key > root->val) {
    
                root->right = deleteNode(root->right, key);
            } else if(key < root->val) {
    
                root->left = deleteNode(root->left, key);
            } else {
    
                if(root->right) {
    
                    if(root->right->left) {
    
                        auto t = root->right;
                        auto pre = t;
                        while(t->left) {
    
                            pre = t;
                            t = t->left;
                        }
                        root->val = t->val;
                        pre->left = t->right;
                        delete t;
                    } else {
    
                        root->val = root->right->val;
                        auto t = root->right;
                        root->right = root->right->right;
                        delete t;
                    }
                } else if(root->left) {
    
                    if(root->left->right) {
    
                        auto t = root->left;
                        auto pre = t;
                        while(t->right) {
    
                            pre = t;
                            t = t->right;
                        }
                        root->val = t->val;
                        pre->right = t->left;
                        delete t;
                    } else {
    
                        root->val = root->left->val;
                        auto t = root->left;
                        root->left = root->left->left;
                        delete t;
                    }
                }
                else {
    
                    return nullptr;
                }
            }
            return root;
        }
};

执行结果