1.2 二叉搜索树中等题

701.?二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点?root?和要插入树中的值?value?，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据?保证?，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回?任意有效的结果?。

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

?思路1：

不考虑需要“旋转节点”，则只需要找到可插入该Val的空节点位置即可

细节：在二叉搜索树中左节点<根节点<右节点

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) return new TreeNode(val);
        //没有相等的情况
        if(val>root->val)
        {
            if(root->right)
            {
                insertIntoBST(root->right,val);
            }
            else
            {
                //则插入该空节点
                root->right=new TreeNode(val);
                return root;
            }
        }
        else 
        {
            if(root->left)
            {
                insertIntoBST(root->left,val);
            }
            else
            {
                //则插入该空节点
                root->left=new TreeNode(val);
                return root;
            }
        }
        return root;
    }
};

?

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

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

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

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

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

?思路1：

和插入类似，首先进行“查找”，找到了对应的节点，再进行删除节点操作

细节：

删除操作需要考虑的情况比较多：需要delete释放“key节点”空间

1.没有该key值的节点

2.该key值是根节点

? ? ? ? （1）无孩子节点

? ? ? ? ? ? ? ? ? ? ? ? 返回nullptr

? ? ? ? （2）孩子节点中一个为nullptr，一个非空

? ? ? ? ? ? ? ? ? ? ? ? 返回非空的孩子节点

? ? ? ? （3）左右孩子节点都不为空

? ? ? ? ? ? ? ? ? ? ? ? 将左孩子的节点都放到右孩子节点的最左下角去，并返回右孩子节点

                TreeNode* curRoot=cur->right,*curRootLeftMax=cur->right;
                TreeNode* curInsert=cur->left;
                //找到右孩子节点的最左下角
                while(curRootLeftMax->left)
                {
                    curRootLeftMax=curRootLeftMax->left;
                }
                //插入左下角
                curRootLeftMax->left=curInsert;
                return curRoot;

3.该key值非根节点

? ? ? ? （1）无孩子节点

? ? ? ? ? ? ? ? ? ? ? ? 删除该节点

            if(!cur->left&&!cur->right)
            {
                if(father->left==cur)
                {
                    father->left=nullptr;
                    return root;
                }
                else{
                    father->right=nullptr;
                    return root;
                }
            }

? ? ? ? （2）孩子节点中一个为nullptr，一个非空

? ? ? ? ? ? ? ? ? ? ? ? 返回非空的孩子节点

? ? ? ? （3）左右孩子节点都不为空

? ? ? ? ? ? ? ? ? ? ? ? 将左孩子的节点都放到右孩子节点的最左下角去，并返回右孩子节点

整体代码：

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //进行删除时需要保留父节点,采用迭代法
        if(!root) return nullptr;
        TreeNode* cur=root,*father=nullptr;
        while(cur&&cur->val!=key)
        {
            if(key>cur->val)
            {
                father=cur;
                cur=cur->right;
            }
            else
            {
                father=cur;
                cur=cur->left;
            }
        }
        //没有该key值
        if(!cur) return root;
        //key在root根节点
        else if(father==nullptr)
        {
            //cur没有左右孩子
            if(!cur->left&&!cur->right) return nullptr;
            //其中一个不为nullptr，另一个为nullptr
            else if(!cur->left&&cur->right)
            {
                TreeNode* curRoot=cur->right;
                delete root;
                return curRoot;
            }
            else if(!cur->right&&cur->left)
            {
                TreeNode* curRoot=cur->left;
                delete root;
                return curRoot;
            }
            //cur左右孩子都不为nullptr
            //采用将左孩子的节点都放到右孩子节点的最左下角去
            else if(cur->right&&cur->left)
            {
                TreeNode* curRoot=cur->right,*curRootLeftMax=cur->right;
                TreeNode* curInsert=cur->left;
                //找到右孩子节点的最左下角
                while(curRootLeftMax->left)
                {
                    curRootLeftMax=curRootLeftMax->left;
                }
                //插入左下角
                curRootLeftMax->left=curInsert;
                delete root;
                return curRoot;
            }
        }
        else{
            //cur没有左右孩子
            if(!cur->left&&!cur->right)
            {
                if(father->left==cur)
                {
                    father->left=nullptr;
                    return root;
                }
                else{
                    father->right=nullptr;
                    return root;
                }
            }
            //cur左右孩子其中一个为nullptr
            else if(!cur->left&&cur->right)
            {
                if(father->left==cur)
                {
                    father->left=cur->right;
                }
                else{
                    father->right=cur->right;   
                }
                delete cur;
            }
            else if(!cur->right&&cur->left)
            {
                if(father->left==cur)
                {
                    father->left=cur->left;
                }
                else{
                    father->right=cur->left;   
                }
                delete cur;
            }
            //cur左右孩子都不为nullptr
            //采用将左孩子的节点都放到右孩子节点的最左下角去
            else if(cur->right&&cur->left)
            {
                TreeNode* curRoot=cur->right,*curRootLeftMax=cur->right;
                TreeNode* curInsert=cur->left;
                //找到右孩子节点的最左下角
                while(curRootLeftMax->left)
                {
                    curRootLeftMax=curRootLeftMax->left;
                }
                //插入左下角
                curRootLeftMax->left=curInsert;
                if(father->left==cur)
                {
                    father->left=curRoot;
                }
                else{
                    father->right=curRoot;   
                }
                delete cur;
            }
        }
        return root;
    }
};

这里判断cur是father的左还是右节点，代码比较冗余。

思路2：递归

代码随想录

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            else {
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                root = root->right;     // 返回旧root的右孩子作为新root
                delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};