第二十天，二叉树part07，二叉树搜索树加油加油💪
目录
235.二叉搜索树的最近公共祖先
701.二叉搜索树中的插入操作
450.删除二叉搜索树中的节点
拓展：普通二叉树的删除方式
总结
235.二叉搜索树的最近公共祖先
文档讲解：代码随想录二叉搜索树的最近公共祖先
视频讲解：手撕二叉搜索树的最近公共祖先
题目：
学习：
昨天我们是在普通二叉树内找到公共祖先，采取的是后序遍历的方式，遍历所有的节点，直到找到目标值为止进行返回。
但本题是二叉搜索树，我们可以利用二叉搜索树的特点来进行公共祖先的查找。我们知道二叉搜索树中每个节点的左子树中的所有值一定小于该节点，右子树中的所有值一定大于该节点。依据此特点我们可以把遍历过程分为三种情况。
- p节点的值和q节点的值都小于当前遍历节点的值，则在当前节点的左子树进行寻找。
- p节点的值和q节点的值都大于当前遍历节点的值，则在当前节点的右子树进行寻找。
- p节点的值和q节点的值其中一个等于当前遍历节点的值，或者分别大于，小于当前遍历节点的值，则立马返回当前遍历的节点，该节点就是最小公共祖先。原因：①如果当前节点是p节点或者q节点的其中一个，由于我们是从上至下遍历的，因此剩下一个节点肯定在该节点的子树中，因此当前节点就是最小公共祖先。②当前节点不是p节点或者q节点，此时由于p节点和q节点分别位于当前节点的左右子树之中，因此当前节点肯定是最小公共祖先，否则往左遍历将错过右子树中的节点，往右遍历将错过左子树中的节点。
代码：递归法
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
private:
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
if (cur == NULL) return cur;
// 中
if (cur->val > p->val && cur->val > q->val) { // 左
TreeNode* left = traversal(cur->left, p, q);
return left;
}
else if (cur->val < p->val && cur->val < q->val) { // 右
TreeNode* right = traversal(cur->right, p, q);
return right;
}
else { //第三种情况
return cur;
}
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return traversal(root, p, q);
}
};代码：迭代法
//时间复杂度O(n)
//空间复杂度O(1)
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL) return NULL;
TreeNode* answer = root; //返回数组
while(answer) {
//依据二叉搜索树的特点，分为三种情况
if(p->val > answer->val && q->val > answer->val) {
answer = answer->right;
}
else if(p->val < answer->val && q->val < answer->val) {
answer = answer->left;
}
else { //第三种情况
break;
}
}
return answer;
}
};701.二叉搜索树中的插入操作
文档讲解：代码随想录二叉搜索树中的插入操作
视频讲解：手撕二叉搜索树中的插入操作
题目：
学习：对于二叉搜索树来说只要插入的数据和原始二叉树中的节点不同，则肯定能插入树中并成为一个叶子节点。本题其实不用考虑题目中的改变树的结构的插入方式。
代码：递归法（本题需要插入节点并将更改后的树层层返回）
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
//确定终止条件
if (root == nullptr) {
TreeNode* node = new TreeNode(val);
return node; //把新加入的节点进行返回
}
//确定单层递归逻辑
if(root->val > val) {
root->left = insertIntoBST(root->left, val); //把更改后的树一层层往上返回
}
if(root->val < val) {
root->right = insertIntoBST(root->right, val); //把更改后的树一层层往上返回
}
return root;
}
};450.删除二叉搜索树中的节点
文档讲解：代码随想录删除二叉搜索树中的节点
视频讲解：手撕删除二叉搜索树中的节点
题目：
学习：
本题需要删除二叉搜索树的节点，我们首先要分析的是，删除的情况有哪些：
- 要删除的节点在二叉树中不存在，二叉树不需要修改。
- 要删除的是叶子节点，那直接删除叶子节点，返回nullptr即可。
- 要删除的是中间节点，但中间节点左孩子为空，右孩子不为空，让右孩子替代删除节点。
- 要删除的是中间节点，但中间节点右孩子为空，左孩子不为空，让左孩子替代删除节点。
- 要删除的节点中左右孩子都不为空，则可以将删除节点的左子树的头节点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。(补充一种我采取的方式，使用删除节点的后继或者前序来替代删除节点，但处理会复杂一些）
第5中情况动画说明：
代码：递归法
//时间复杂度O(n)
//空间复杂度O(n)
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;
}
};代码：递归法（使用后继作为代替）
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
//确定终止条件
//没有找到的话
if(root == nullptr) return root;
//找到了的话，分为4种情况
if(root->val == key) {
//第一种情况，要删除的是叶子节点，则直接返回空
if(root->left == nullptr && root->right == nullptr) {
//内存释放
delete root;
return nullptr;
}
//第二种情况，要删除的是中间节点，但是左子树为空，使用右子树节点替代
else if(root->left == nullptr && root->right != nullptr) {
TreeNode* tmp = root;
root = root->right;
delete tmp;
return root;
}
//第三种情况，要删除的是中间节点，但是右子树为空，使用左子树节点替代
else if(root->left != nullptr && root->right == nullptr) {
TreeNode* tmp = root;
root = root->left;
delete tmp;
return root;
}
//第四种情况，要删除的是中间节点，且左右子树都不为空
//使用前驱或者后继节点替代
else {
//使用后继节点替代，即右子树的最左边的节点。
TreeNode* cur = root->right;
TreeNode* pre = nullptr; //指向cur的前一个节点
while(cur->left != nullptr ) {
pre = cur;
cur = cur->left;
}
if(pre == nullptr) { //说明一次循环没有进行，删除节点的右子树的根节点没有左边部分，则其自身就是删除节点的后继
cur->left = root->left; //把删除节点的左子树保留
delete root;
return cur;
}
else { //说明至少进入了循环一次
pre->left = cur->right; //先把cur分理出，并保存cur的右子树（可能为空）
cur->left = root->left; //将删除节点的左右子树释放
cur->right = root->right;
delete root;
return cur;
}
}
}
root->left = deleteNode(root->left, key);
root->right = deleteNode(root->right, key);
return root;
}
};拓展：普通二叉树的删除方式
学习：对于普通二叉树的节点删除来说，可以通过和叶子节点交换值得方式，然后再进行删除。
代码中目标节点（要删除的节点）被操作了两次：第一次是和目标节点的右子树最左面节点交换。第二次直接被NULL覆盖了。
代码：
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root;
if (root->val == key) {
if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用
return root->left;
}
TreeNode *cur = root->right;
while (cur->left) {
cur = cur->left;
}
swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
}
root->left = deleteNode(root->left, key);
root->right = deleteNode(root->right, key);
return root;
}
};总结
二叉搜索树的特点要牢记，利用好二叉树的特点能够更有效的进行算法设计。
