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

在删除一个节点的时候可能有以下情况

• 找不到节点，那么就之间返回最开始的树就好了
• 找到了节点
  • 节点是叶子节点，则直接删掉就好了
  • 节点一边是空的，另一遍是有子树的，则直接把该节点的子节点返回给该节点的前一个节点，然后把这个节点删除
  • 节点两边都是非空的，则把节点的左子树接到右子树的最左面（因为左子树的数值一定全部小于右子树的数值，而右子树的最小值就是右子树最左面的值，所以要把左子树接到右子树的最左面！)

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //没找到节点，则直接返回原树
        if (root == nullptr)return root;
        //找到了节点
        if (root->val == key) {
            //节点是叶子节点
            if (!root->left && !root->right) {
                delete root;
                return nullptr;
            //节点只有一边是空的
            } else if (!root->left && root->right) {
                TreeNode* temp = root->right;
                delete root;
                return temp;
            } else if (root->left && !root->right) {
                TreeNode* temp = root->left;
                delete root;
                return temp;
            //节点两边非空
            } else {
                //这里要注意，因为要找的是右子树最左面，所以要用一个循环来找右子树最左面！！！！
                TreeNode* cur = root->right;
                while (cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left;
                TreeNode* temp = root->right;
                delete root;
                return temp;
            }
        }
        //其实上面都算得上是递归终止条件的部分，下面是我个人最不会的部分：递归单层逻辑
        //这里主要是利用二叉搜索树来找哪一个子树要修改（即删除子节点）
        //删除操作其实是一种父子节点间赋值的操作！！！这种要上下联动的操作用有
        //返回值的递归函数来解比较方便，如果用没有返回值的递归来解，则要多一个
        //pre节点来记录上一个节点，比较麻烦!
        if (root->val > key)root->left = deleteNode(root->left, key);
        if (root->val < key)root->right = deleteNode(root->right, key);
        return root;
    }
};