二叉搜索树中的插入操作

力扣题目链接(opens new window)

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

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

提示：

• 给定的树上的节点数介于 0 和 10^4 之间
• 每个节点都有一个唯一整数值，取值范围从 0 到 10^8
• -10^8 <= val <= 10^8
• 新值和原始二叉搜索树中的任意节点值都不同

思路

就正常遍历二叉搜索树，因为二叉搜索树的性质，我们可以通过当前值大小控制遍历方向：

​ 如果待插入节点小于当前节点，那么继续向当前节点的左子树遍历，重复比较。

​ 直到遇到大于当前节点的情况，那么此时开始向右遍历，找到比待插入值小的当前遍历节点

当遍历到叶子节点，我们就使用插入值创建一个新节点并返回给上层递归调用者

通过层层传递，最后就在原二叉搜索树的一个对应分支的末尾插入了新节点

class Solution {
public:
    //确定递归函数的返回值和参数
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        //确定终止条件
        //当遍历到叶子节点了，就直接把待插入的树加上就行了，然后返回给上层递归调用者
        //通过一层层返回就形成了树的连接
        //因为是按照搜索树顺序遍历的，所以不用看大小了都
        if(root == NULL){
            TreeNode* node = new TreeNode(val);//创建一个新节点并返回
            return node;
        }      
        //因为是二叉搜索树，所以我们没有必要遍历整颗树
        //可以通过当前节点值的大小来控制遍历方向
        if(val < root->val){
            root->left = insertIntoBST(root->left, val);//左
        }else if(val > root->val){
            root->right = insertIntoBST(root->right,val);//右
        }
        return root;
    }
};

二叉搜索树中的删除操作（情况很多）

力扣题目链接(opens new window)

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

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

首先找到需要删除的节点； 如果找到了，删除它。 说明： 要求算法时间复杂度为 $O(h)$，h 为树的高度。

示例:

思路

我们想删除节点，首先得找到待删除的节点位置吧

那么在本题中，待删除节点的位置一共可能有以下几种情况:

• 树中不存在待删除节点
• 找到待删除节点，其左子树节点为空，右子树节点不为空
• 找到待删除节点，其左子树节点不为空，右子树节点为空
• 找到待删除节点，其左子树节点不为空，右子树节点也不为空（重点）
• 找到待删除节点，没有左右子节点

下面逐一分析应对方法

• 没找到删除节点

  • 遍历到空节点直接返回了

• 找到待删除节点

  • 其左子树节点为空，右子树节点不为空，直接把当前节点删除，让右子节点补位即可
  • 左子树节点不为空，右子树节点为空，直接把当前节点删除，让左子节点补位即可
  • 没有左右子节点，直接删除当前节点，然后返回NULL节点

  以上两种补位的情况，图解如下：

单独说一下左右不为空的情况

如果待删除节点的左右子节点不为空，这时候就涉及到调整二叉树的结构

由于二叉搜索树的性质，左子树的值均小于根节点

那么当前节点删除后，左子树的节点是不可能直接放到删除节点的位置的

删掉的节点需要由右子节点补位

而删除节点的左子树需要整颗接到删除节点的右子树的最左边节点的左子节点处

这个规则看似很复杂，但其实想想也说得通，下面通过图示具体说明

如图所示，节点7为待删除节点，其左右子节点均不为空

当删除节点7后，根据二叉搜索树的规则，我们只能将节点7的右子节点9用于补位

因为如果用节点5（也就是左子节点），那么节点9不论接到其后的哪个节点，均不能满足二叉搜索树的定义

即以下两种情况：

回到题目

因为在二叉搜索树中，待删除节点7一定小于其右子树的所有节点值，且一定大于其左子树的所有子节点值

所以，待删除节点7左子树的所有子节点值一定是小于当前待删除节点7有子树的所有子节点值的

因此，当节点9补位被删掉的节点7后，节点7的左子树（以节点5为根节点）需要整体接到节点8的位置（以当前图示为例，即待删除节点的右子树的最左节点的左子树，因为这里为待删除节点的右子树中值最小的位置）

代码

递归法

还是递归三部曲

1、确定递归函数的参数和返回值

因为我们需要通过递归的回溯（即返回值）来添加移动或补位的节点，所以递归函数中是需要返回值的

（简明理解：根节点root最初调用了递归，当递归的最后一层完成了操作，所有结果需要层层返回，最后返回到最初的根节点root处，即完成了对二叉树的修改）

那么解题模板可以直接使用

class Solution {
public:
    //确定递归函数的参数和返回值
    TreeNode* deleteNode(TreeNode* root, int key) {

    }
};

2、确定终止条件

这里的终止条件指的是“如果没找到待删除节点，那么不能让递归无限循环下去”

因此只需要写出思路分析中的“树中不存在待删除节点”的情况

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //确定终止条件
		if(root = NULL) return root;
    }
};

3、确定单层处理逻辑

单层处理逻辑对应着找到待删除节点的四种情况

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //确定终止条件
		if(root = NULL) return root;
        
        //确定单层处理逻辑
        //如果找到了待删除值
        //没有左右子节点
        
        if(root->val == key){
            if (root->left == nullptr && root->right == nullptr) {
                //直接删除节点并内存释放
                delete root;
                return nullptr;
            }
            //其左子树节点为空，右子树节点不为空，返回被删除节点的右子树（的根节点）
            // else if(root->left == nullptr) return root->right;
            //不能像上面那样写，因为还要删root，得用一个临时node接一下root->right
            else if(root->left == nullptr){
                //接一下root->right
                auto resNode = root->right;
                delete root;//删root
                return resNode;
            }


            //其右子树节点为空，左子树节点不为空，返回被删除节点的左子树（的根节点）
            // else if(root->right == nullptr) return root->left;//同理
            else if(root->right == nullptr){
                auto resNode = root->left;
                delete root;
                return resNode;
            }
        }    
    }
};

接下来处理待删除节点的左右子节点不为空的情况

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        //确定终止条件
		if(root == nullptr) return root;
        
        //确定单层处理逻辑
        //如果找到了待删除值
        //没有左右子节点
        
        if(root->val == key){
            if (root->left == nullptr && root->right == nullptr) {
                //直接删除节点并内存释放
                delete root;
                return nullptr;
            }
            //其左子树节点为空，右子树节点不为空，返回被删除节点的右子树（的根节点）
            // else if(root->left == nullptr) return root->right;
            //不能像上面那样写，因为还要删root，得用一个临时node接一下root->right
            else if(root->left == nullptr){
                //接一下root->right
                auto resNode = root->right;
                delete root;//删root
                return resNode;
            }
            //其右子树节点为空，左子树节点不为空，返回被删除节点的左子树（的根节点）
            // else if(root->right == nullptr) return root->left;//同理
            else if(root->right == nullptr){
                auto resNode = root->left;
                delete root;
                return resNode;
            }
            else{//待删除节点的左右子节点不为空
                //先去遍历待删除节点的右子树的左分支，找到最左边的节点
                //定义一个指针
                TreeNode* cur = root->right;
                while(cur->left != nullptr){//遍历右子树的左分支
                    cur = cur->left;
                }//循环结束就找到了最左节点
                //删除root节点并移动其左子树
                //把要删除的节点（root）左子树放在cur的左子节点的位置
                cur->left = root->left;
                //保存一下当前的root节点，待会要把它指向其右子节点
                TreeNode* temp = root;//保证删除root时删的是root，而不是修改后的root->right
                //root被其右子节点补位
                root = root->right;
                //删除temp、root
                delete temp;
                return root;  
            }
        }
        //还没找到待删除值就继续调用递归去找
        if(root->val > key){
            root->left = deleteNode(root->left, key);//相当于把之后调整的新节点返回回来，并用left接收
            //如果目标值在左子树被发现，那么左子树结构肯定变化，因此需要返回新的节点
        }else if(root->val < key){
            root->right = deleteNode(root->right, key);//同理
        } 
        return root;   
    }
};

迭代法

TBD

天坑

本题的思路过得差不多了

但在coding时遇到了很多问题

1、删除一个节点的正确方法

先使用一个临时节点把待删除节点保存，然后让该节点指向你规定的下一个节点（链表基础遗忘）

//其左子树节点为空，右子树节点不为空，返回被删除节点的右子树（的根节点）
            // else if(root->left == nullptr) return root->right;
            //不能像上面那样写，因为还要删root，得用一个临时node接一下root->right
            else if(root->left == nullptr){
                //接一下root->right
                auto resNode = root->right;
                delete root;//删root
                return resNode;
            }

2、NULL和nullptr的区别

参考

在C++中，NULL为整数0；nullptr代表空指针

3、内存泄漏

内存泄漏比较难以定位，通常报错如下：

-----=-42==ERROR: AddressSanitizer: heap-use-after-free on address 0x60300000100 at pc 0x0000034fc9 bp 0x7fff5d8c78d0 sp 0x7ff5d8c78c8READ of size 4 at 0x603000000100 thread TO
#3 0x7faf469e4082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)0x603000000100 is ocated 0 bytes inside of 24-byte region [0x603000000100,0x603000000118)freed by thread To here:
#4 0x7faf469e4082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)previously allocated by thread To here:
#4 0x7faf469e4082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)Shadow bytes around the buggy address :
0x0c067fff7fdo: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c067fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 0 00 00 00 000x0c067fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

这是一个AddressSanitizer检测到的错误，指出在程序运行时使用了一个已经释放的内存地址

一般来说，是某处使用指针没有释放，或者对指针进行了不正确的操作导致的

可以照着这个思路排除所有使用指针的地方
（做这题的时候™的就是return写成delete了，即错误操作了某个指针导致报错）