1. 二叉搜索树的最近公共祖先
代码随想录：原文
力扣题目： 235. 二叉搜索树的最近公共祖先
1.1 思路
- 二叉搜索树是有序的
- 因为是有序树，所有 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p
- 当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[p, q]区间中，那么cur就是 p和q的最近公共祖先
1. 确定递归函数返回值以及参数
- 参数就是当前节点，以及两个结点 p、q
- 返回值是要返回最近公共祖先，所以是TreeNode *
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
2. 确定终止条件
- 遇到空返回
if (cur == NULL) return cur;
3. 确定单层递归的逻辑
- 遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭右闭）
- 如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历（说明目标区间在左子树上）
- 注意： 此时不知道p和q谁大，所以两个都要判断
if (cur->val > p->val && cur->val > q->val) {
TreeNode* left = traversal(cur->left, p, q);
if (left != NULL) {
return left;
}
}
- 如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历
if (cur->val < p->val && cur->val < q->val) {
TreeNode* right = traversal(cur->right, p, q);
if (right != NULL) {
return right;
}
}
- cur节点在区间[p q] 中，那么cur就是最近公共祖先了，直接返回cur
return cur;
1.2 代码实现
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);
if (left != NULL) {
return left;
}
}
if (cur->val < p->val && cur->val < q->val) { // 右
TreeNode* right = traversal(cur->right, p, q);
if (right != NULL) {
return right;
}
}
return cur;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return traversal(root, p, q);
}
};
2. 二叉搜索树中的插入操作
代码随想录：原文
力扣题目： 701.二叉搜索树中的插入操作
2.1 思路
遍历二叉搜索树，找到空节点 插入元素就可以了
1. 确定递归函数参数以及返回值
- 参数就是根节点指针，以及要插入元素
- 有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作
- 递归函数的返回类型为节点类型TreeNode *
TreeNode* insertIntoBST(TreeNode* root, int val)
2. 确定终止条件
终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
3. 确定单层递归的逻辑
- 搜索树是有方向了，可以根据插入元素的数值，决定递归方向
- 本层用root->left或者root->right将其接住
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
2.2 代码实现
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) {
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;
}
};
3. 删除二叉搜索树中的节点
代码随想录：原文
力扣题目： 450.删除二叉搜索树中的节点
3.1 思路
1. 确定递归函数参数以及返回值
- 参数： 二叉搜索树根节点，删除的值
- 返回：删除后二叉搜索树根节点
TreeNode* deleteNode(TreeNode* root, int key)
2. 确定终止条件
- 遇到空返回，其实这也说明没找到删除的节点
if (root == nullptr) return root;
3. 确定单层递归的逻辑
有以下五种情况：
- 第一种情况：没找到删除的节点，遍历到空节点直接返回了
- 第二种情况：找到删除的节点，左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
- 第三种情况：找到删除的节点，删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
- 第四种情况：找到删除的节点，删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
- 第五种情况：找到删除的节点，左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
if (root->val == key) {
// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
// 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
if (root->left == nullptr) return root->right;
// 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
else if (root->right == nullptr) return root->left;
// 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
// 并返回删除节点右孩子为新的根节点。
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;
}
}
- 这里相当于把新的节点返回给上一层，上一层就要用 root->left 或者 root->right接住，代码如下：
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
3.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;
}
};
4. 总结
- 二叉搜索树的最近祖先问题非常简单
- 二叉搜索树插入元素不需要调整二叉树的结构
- 遇到复杂情况一定要想清楚情况再写
学习时间：130min
评论区