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

分析

1. 如果目标节点大于当前节点值，则去右子树中删除；
2. 如果目标节点小于当前节点值，则去左子树中删除；
3. 如果目标节点就是当前节点，分为以下三种情况：

• 其无左子：其右子顶替其位置，删除了该节点；
• 其无右子：其左子顶替其位置，删除了该节点；
• 其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点

/**
 * 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==nullptr)return nullptr;
        if(root->val>key){
            root->left= deleteNode(root->left,key);
        }else if(root->val<key){
            root->right=deleteNode(root->right,key);
        }else{
           if(root->left==nullptr)return root->right;
           if(root->right==nullptr)return root->left;
           TreeNode *temp=root->right;
           while(temp->left)temp=temp->left;
           temp->left=root->left;
           root=root->right;
        }
        return root;
    }
};