【20221105】【每日一题】删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

---

 思路：在找到要删除的点后，分为几种情况，其中节点的左右孩子均不为空的时候复杂一点，要考虑的左右孩子都可能不为一层，统一化的办法就是用右孩子去继承，将左孩子放在右孩子的最左侧的节点下面，这样可以保证重构后仍然为二叉搜索树。

这里的终止条件也要注意一下，不需要将整个二叉树都遍历完，找到目标点就可以了。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==NULL)  return NULL;
        //找到删除节点的情况
        if(root->val==key)
        {
            //1.删除的节点正好为叶子节点，直接删除即可
            if(root->left==NULL&&root->right==NULL)
            {
                delete root;
                return NULL;
            }
            //2.删除的节点有一个孩子，让那个孩子来代替它的位置
            else if(root->left==NULL&&root->right!=NULL)
            {
                TreeNode* reNode=root->right;
                delete root;
                return reNode;
            }
            else if(root->left!=NULL&&root->right==NULL)
            {
                TreeNode* reNode=root->left;
                delete root;
                return reNode;
            }
            //3.删除的节点有两个孩子，这时候其实有不同的构造方式，这里就统一一下
            //用右孩子代替被删除的节点，左孩子成为新节点的左孩子
            //注意这里如果删除的节点下面不止一层，（自己考虑的时候就漏了这类情况）
            //将整个左子树放在右子树的最左侧的节点下面，可以保证为二叉搜索树
            else
            {
                TreeNode* cur=root->right;
                //cur指向右子树的最左侧的节点
                while(cur->left)
                {
                    cur=cur->left;
                }
                cur->left=root->left;
                root=root->right;
                return root;
            }
        }
        if(root->val>key)   root->left=deleteNode(root->left,key);
        if(root->valright=deleteNode(root->right,key);
        return root;  
    }
};