题目描述

原题链接：450. 删除二叉搜索树中的节点

解题思路

1. 在删除操作时，要可获取父节点。
2. 对于结点值等于key的结点，删除可能会出现三种情况。
   （1）左、右子树都为空，则直接返回NULL；
   （2）当一侧为空，一侧不为空，则返回不为空的孩子；
   （3）当左、右两侧都不为空，则将一侧孩子插入另一侧下面，再返回新构建的孩子。

1、先序遍历递归法

采用递归的方式，未找到时，根据值的大小，向对应一侧遍历，让其指针指向对应一侧。找到时，对节点进行处理后，返回节结点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root)       return NULL;   
        if(root->val == key) {
            if(!root->left && !root->right)
                return NULL;
            TreeNode* temp = root;                      // temp用于删除该结点
            if(root->left && !root->right) {            // 左不空，右空，返回左    
                root =  root->left;
            } else if(root->right && !root->left) {     // 左空，右不空，返回右
                root =  root->right;
            } else if(root->left && root->right) {      // 左右都不空，将右插入到左的最右边
                TreeNode* cur = root->left;
                while(cur->right)       cur = cur->right;
                cur->right = root->right;       // 插入左孩子的右下角
                root = root->left;                      // 返回左孩子
            }
            delete temp;        // 删除等于key的结点
            return root;
        }
        // 左、右向下遍历时，已经包含了父节点指向的关系，只需对找到结点处理即可。
        if(root->val > key)          root->left = deleteNode(root->left, key);        
        else if(root->val < key)     root->right = deleteNode(root->right, key);
        return root;        
    }
};

2、迭代法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* transformTree(TreeNode* cur, int key) {    
        TreeNode* node = cur;        
        if(!cur->left && !cur->right) {             // 左右无孩子，直接返回NULL
            return NULL;
        } else if (!cur->left) {                    // 左空，右不空，node指向右
            node = cur->right;
        } else if (!cur->right) {                   // 右空，左不空，node指向左
            node = cur->left;
        } else if (cur->left && cur->right) {       // 左右都不空，让左子树的右下角结点指向，右子树
            TreeNode* p = cur->left;
            while(p->right)     p = p->right;
            p->right = cur->right;
            node = cur->left;                       // 让node指向左子树
        }   
        return node;
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root)       return NULL;
        // 寻找删除点
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while(cur) {
            if(cur->val == key)        break;
            pre = cur;
            if(cur->val > key)  cur = cur->left;
            else                cur = cur->right;
        }
        // 没找到，则直接返回root
        if(!cur)        return root;       
        // 若删除的为根节点，改变root的值
        if(!pre)        root = transformTree(cur, key);
        // 当删除的为某结点的左孩子
        else if(pre->left && pre->left->val == key)
            pre->left = transformTree(cur, key);
        // 当删除的为某结点的右孩子
        else if(pre->right && pre->right->val == key)
            pre->right = transformTree(cur, key);
        // 删除该结点
        delete cur;
        return root;
    }
};

参考文章：450.删除二叉搜索树中的节点