算法训练day22Leetcode236二叉搜索树的最近祖先701二叉搜索树中的插入操作450删除二叉搜索树中的节点

2024-01-29 09:20
文章标签 算法 训练 操作 搜索 二叉 删除 树中 插入 节点 最近 祖先 450 701 day22leetcode236

本文主要是介绍算法训练day22Leetcode236二叉搜索树的最近祖先701二叉搜索树中的插入操作450删除二叉搜索树中的节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

235 二叉搜索树的最近公共祖先

题目描述

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

我的想法

利用二叉搜索树特性遍历，从上到下遍历

题目分析

在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？

因为是有序树，所有 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。

递归法
递归三部曲如下：

  1. 确定递归函数返回值以及参数
    参数就是当前节点，以及两个结点 p、q。

返回值是要返回最近公共祖先，所以是TreeNode * 。

代码如下：

TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
  1. 确定终止条件
    遇到空返回就可以
if (cur == nullptr) return cur;

其实都不需要这个终止条件，因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的，所以并不存在遇到空的情况。

  1. 确定单层递归逻辑
    在遍历二叉搜索树的时候就是寻找区间[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;}
}

如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树。

搜索一条边的写法：
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
搜索整个树写法：left = 递归函数(root->left);
right = 递归函数(root->right);

left与right的逻辑处理;
本题就是标准的搜索一条边的写法，遇到递归函数的返回值，如果不为空，立刻返回。

如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历（目标区间在右子树）。

剩下的情况，就是cur节点在区间（p->val <= cur->val && cur->val <= q->val）或者 （q->val <= cur->val && cur->val <= p->val）中，那么cur就是最近公共祖先了，直接返回cur。

acm模式代码

#include <iostream>
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}
};class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr) return nullptr;if (root->val > p->val && root->val > q->val) {TreeNode* left = lowestCommonAncestor(root->left, p, q);if (left != nullptr) return left;    }if (root->val < p->val && root->val < q->val) {TreeNode* right = lowestCommonAncestor(root->right, p, q);if (right != nullptr) return right;}return root;}
};int main() {// Example tree creationTreeNode* root = new TreeNode(6);root->left = new TreeNode(2);root->right = new TreeNode(8);root->left->left = new TreeNode(0);root->left->right = new TreeNode(4);root->left->right->left = new TreeNode(3);root->left->right->right = new TreeNode(5);root->right->left = new TreeNode(7);root->right->right = new TreeNode(9);Solution sol;TreeNode* p = root->left; // For example, node with value 2TreeNode* q = root->right; // For example, node with value 8TreeNode* lca = sol.lowestCommonAncestor(root, p, q);if (lca != nullptr) {std::cout << "Lowest Common Ancestor: " << lca->val << std::endl;} else {std::cout << "No common ancestor found." << std::endl;}// Clean up memorydelete root->left->right->right;delete root->left->right->left;delete root->left->right;delete root->left->left;delete root->right->right;delete root->right->left;delete root->left;delete root->right;delete root;return 0;
}

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

题目描述

https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

我的想法

采用中序遍历

题目分析

只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了

递归三部曲：

  1. 确定递归函数参数以及返回值
    参数就是根节点指针，以及要插入元素，这里递归函数要不要有返回值呢？

可以有，也可以没有，但递归函数如果没有返回值的话，实现是比较麻烦的，下面也会给出其具体实现代码。

有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作。（下面会进一步解释）

递归函数的返回类型为节点类型TreeNode * 。

代码如下：

TreeNode* insertIntoBST(TreeNode* root, int val)
  1. 确定终止条件
    终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。

代码如下：

if (root == NULL) {TreeNode* node = new TreeNode(val);return node;
}

这里把添加的节点返回给上一层，就完成了父子节点的赋值操作了，详细再往下看。

  1. 确定单层递归逻辑

    此时要明确，需要遍历整棵树么？

别忘了这是搜索树，遍历整棵搜索树简直是对搜索树的侮辱。

搜索树是有方向了，可以根据插入元素的数值，决定递归方向。

代码如下：

if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;

acm模式代码

#include <iostream>
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}
};class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr) return nullptr;if (root->val > p->val && root->val > q->val) {TreeNode* left = lowestCommonAncestor(root->left, p, q);if (left != nullptr) return left;    }if (root->val < p->val && root->val < q->val) {TreeNode* right = lowestCommonAncestor(root->right, p, q);if (right != nullptr) return right;}return root;}
};int main() {// Example tree creationTreeNode* root = new TreeNode(6);root->left = new TreeNode(2);root->right = new TreeNode(8);root->left->left = new TreeNode(0);root->left->right = new TreeNode(4);root->left->right->left = new TreeNode(3);root->left->right->right = new TreeNode(5);root->right->left = new TreeNode(7);root->right->right = new TreeNode(9);Solution sol;TreeNode* p = root->left; // For example, node with value 2TreeNode* q = root->right; // For example, node with value 8TreeNode* lca = sol.lowestCommonAncestor(root, p, q);if (lca != nullptr) {std::cout << "Lowest Common Ancestor: " << lca->val << std::endl;} else {std::cout << "No common ancestor found." << std::endl;}// Clean up memorydelete root->left->right->right;delete root->left->right->left;delete root->left->right;delete root->left->left;delete root->right->right;delete root->right->left;delete root->left;delete root->right;delete root;return 0;
}

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

题目描述

https://leetcode.cn/problems/delete-node-in-a-bst/description/

题目分析

搜索树的节点删除要比节点增加复杂的多，有很多情况需要考虑

递归
递归三部曲：

  1. 确定递归函数参数以及返回值

说到递归函数的返回值，在二叉树：搜索树中的插入操作 (opens new window)中通过递归返回值来加入新节点， 这里也可以通过递归返回值删除节点。

代码如下：

TreeNode* deleteNode(TreeNode* root, int key)
  1. 确定终止条件

遇到空返回，其实这也说明没找到删除的节点，遍历到空节点直接返回了

if (root == nullptr) return root;
  1. 确定单层递归的逻辑
    这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了

找到删除的节点

第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回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的右孩子作为新rootdelete 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;

acm模式代码

#include <iostream>
struct TreeNode
{int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}
};class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {//1.确定终止条件if (root == nullptr) {return nullptr;}if (root->val == key) {//左右子树都为空,说明自身是叶子节点if (root->left == nullptr && root->right == nullptr) {return nullptr;}//左子树为空，右子树不为空else if (root->left == nullptr && root->right != nullptr) {return root->right;}//左子树不为空，右子树为空else if (root->left != nullptr && root->right == nullptr) {return root->left;}//左右子树都不为空else {TreeNode* cur = root->right;while (cur->left != nullptr) {cur = cur->left;}cur->left = root->left;return root->right ;}}//2.确定单层递归if (root->val > key) {root->left = deleteNode(root->left, key);}else if (root->val < key) {root->right = deleteNode(root->right, key);}return root;}
};void printInOrder(TreeNode* node) {if (node == nullptr) {return;}printInOrder(node->left);std::cout << node->val << " ";printInOrder(node->right);
}void deleteTree(TreeNode* node) {if (node == nullptr) {return;}deleteTree(node->left);deleteTree(node->right);delete node;
}int main() {// 创建测试树TreeNode* root = new TreeNode(5);root->left = new TreeNode(3);root->right = new TreeNode(6);root->left->left = new TreeNode(2);root->left->right = new TreeNode(4);root->right->right = new TreeNode(7);// 打印原始树std::cout << "原始树的中序遍历: ";printInOrder(root);std::cout << std::endl;// 删除节点Solution solution;root = solution.deleteNode(root, 3); // 例如，删除值为3的节点// 打印更新后的树std::cout << "删除节点后的中序遍历: ";printInOrder(root);std::cout << std::endl;// 清理分配的内存deleteTree(root);
}

今日学习链接

https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E6%80%9D%E8%B7%AF

这篇关于算法训练day22Leetcode236二叉搜索树的最近祖先701二叉搜索树中的插入操作450删除二叉搜索树中的节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/656441。

相关文章

Jmeter如何向数据库批量插入数据

Jmeter如何向数据库批量插入数据

《Jmeter如何向数据库批量插入数据》：本文主要介绍Jmeter如何向数据库批量插入数据方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Jmeter向数据库批量插入数据Jmeter向mysql数据库中插入数据的入门操作接下来做一下各个元件的配置总结Jmete
阅读更多...
SpringBoot操作MaxComputer方式(保姆级教程)

SpringBoot操作MaxComputer方式(保姆级教程)

《SpringBoot操作MaxComputer方式(保姆级教程)》：本文主要介绍SpringBoot操作MaxComputer方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的... 目录引言uqNqjoe一、引入依赖二、配置文件 application.properties（信息用自己
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
Python使用DeepSeek进行联网搜索功能详解

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例：图像分类1.
阅读更多...
C#中的 Dictionary常用操作

C#中的 Dictionary常用操作

《C#中的Dictionary常用操作》C#中的DictionaryTKey,TValue是用于存储键值对集合的泛型类,允许通过键快速检索值,并且具有唯一键、动态大小和无序集合的特性,常用操作包括添... 目录基本概念Dictionary的基本结构Dictionary的主要特性Dictionary的常用操作
阅读更多...
C# winform操作CSV格式文件

C# winform操作CSV格式文件

《C#winform操作CSV格式文件》这篇文章主要为大家详细介绍了C#在winform中的表格操作CSV格式文件的相关实例,文中的示例代码讲解详细,感兴趣的小伙伴可以参考一下... 目录实例一实例效果实现代码效果展示实例二实例效果完整代码实例一实例效果当在winform界面中点击读取按钮时 将csv中
阅读更多...
MySQL InnoDB引擎ibdata文件损坏/删除后使用frm和ibd文件恢复数据

MySQL InnoDB引擎ibdata文件损坏/删除后使用frm和ibd文件恢复数据

《MySQLInnoDB引擎ibdata文件损坏/删除后使用frm和ibd文件恢复数据》mysql的ibdata文件被误删、被恶意修改,没有从库和备份数据的情况下的数据恢复,不能保证数据库所有表数据... 参考：mysql Innodb表空间卸载、迁移、装载的使用方法注意！此方法只适用于innodb_fi
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
shell脚本自动删除30天以前的文件(最新推荐)

shell脚本自动删除30天以前的文件(最新推荐)

《shell脚本自动删除30天以前的文件(最新推荐)》该文章介绍了如何使用Shell脚本自动删除指定目录下30天以前的文件,并通过crontab设置定时任务,此外,还提供了如何使用Shell脚本删除E... 目录shell脚本自动删除30天以前的文件linux按照日期定时删除elasticsearch索引s
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2