【算法训练营day22】LeetCode235. 二叉搜索树的最近公共祖先 LeetCode701. 二叉搜索树中的插入操作 LeetCode450. 删除二叉搜索树中的节点
2023-04-18 12:37:48 时间
LeetCode235. 二叉搜索树的最近公共祖先
题目链接:235. 二叉搜索树的最近公共祖先
初次尝试
利用二叉搜索树的性质,迭代法即可,判断目标节点的值是否在当前节点值的两侧或与当前节点值相等,如果满足,当前节点即为最近公共祖先,否则就向着目标节点值的方向继续搜索。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (root != NULL) {
long long root_p = root -> val - p -> val;
long long root_q = root -> val - q -> val;
if (root_p * root_q <= 0) return root;
else if (root_p > 0) root = root -> left;
else root = root -> right;
}
return NULL;
}
};
看完代码随想录后的想法
思路差不多。
LeetCode701. 二叉搜索树中的插入操作
题目链接:701. 二叉搜索树中的插入操作
初次尝试
利用二叉搜索树的性质的迭代法,将插入值与当前节点值进行比较,从而确定搜索路径,当遇到空节点时,将新节点插入。
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
TreeNode* new_node = new TreeNode(val);
TreeNode* node = root;
if (!root) return new_node;
while (node) {
if (!node -> left && node -> val > val) {
node -> left = new_node;
break;
}
else if (!node -> right && node -> val < val) {
node -> right = new_node;
break;
}
if (node -> val > val) node = node -> left;
else node = node -> right;
}
return root;
}
};
看完代码随想录后的想法
思路差不多。
LeetCode450. 删除二叉搜索树中的节点
题目链接:450. 删除二叉搜索树中的节点
初次尝试
感觉解法会比较复杂,没有想到什么容易实现的思路。
看完代码随想录后的想法
和我一开始的思路很像,果然很复杂,需要讨论很多种情况。
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;
}
};
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击