代码随想录算法训练营Day22|235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

本文主要是介绍代码随想录算法训练营Day22|235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

不考虑二叉搜索树这一条件的话,普通的二叉搜索树搜索最近的公共祖先就是昨日的做法,这种做法也能解决二叉搜索树的最近公共祖先。

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 如果当前节点为空,或者等于p或q,直接返回当前节点if (root == nullptr || root == p || root == q) {return root;}// 在左右子树中递归寻找p和qTreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);// 如果左右子树的返回值都不为空,说明当前节点就是最近公共祖先if (left != nullptr && right != nullptr) {return root;}// 否则,返回非空的子树返回值return left != nullptr ? left : right;}
};

没有用上二叉搜索树这一条件,但也能解题,但效率较低。

针对二叉搜索树,我们之前有做过,当对二叉搜索树进行中序编历时,结果是一个递增的数组。即公共祖先,val值必定处于p和q之间。

当从根节点向下遍历的过程中,如果遇到节点val值位于p和q之间,那么就寻找到了最近的公共祖先。具体参考代码随想录B站视频。

二叉搜索树找祖先就有点不一样了!| 235. 二叉搜索树的最近公共祖先_哔哩哔哩_bilibiliicon-default.png?t=N7T8https://www.bilibili.com/video/BV1Zt4y1F7ww/?spm_id_from=333.788&vd_source=fc4a6e70e3a87b7ea67c2024e326e7c5从上到下遍历,考虑层序遍历的方式,具体代码如下:

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {queue<TreeNode*>queue;if(root == nullptr){return nullptr;}queue.push(root);TreeNode*cur = root;int min = p->val>q->val?q->val:p->val;//找到p,q中val的较小值int max = p->val<q->val?q->val:p->val;//找到p,q中val的较大值while(!queue.empty()){//层序遍历过程int level_size = queue.size();for(int i = 0; i <level_size; i ++){cur = queue.front();queue.pop();if(cur->val<=max and cur->val>=min){return cur;}//找到节点属于p,q间则返回if(cur->left)queue.push(cur->left);if(cur->right)queue.push(cur->right);} }return nullptr;}
};

算法的时间复杂度和空间复杂度均为O(n)。

前序递归,中左右,参考代码随想录

代码随想录 (programmercarl.com)icon-default.png?t=N7T8https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html#%E6%80%9D%E8%B7%AF

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);}
};

二叉搜索树中的插入操作

由于树中的节点值是独一无二的,在二叉搜索树中寻找值应插入的节点的父节点位置,然后创建一个新节点并将其插入即可。

代码整体如下

class Solution {
public:// 在二叉搜索树中查找适合插入新节点的位置,并返回该位置的父节点TreeNode* findBST(TreeNode* root, int val) {// 如果当前节点为空,返回nullptr,表示没有找到合适的插入位置if (root == nullptr) return nullptr;// 如果val小于当前节点的值,应该在左子树中继续查找if (val < root->val) {// 如果左子节点为空,当前位置就是适合插入新节点的位置if (root->left == nullptr) return root;// 否则,在左子树中继续查找return findBST(root->left, val);} else {// 如果val大于或等于当前节点的值,应该在右子树中继续查找// 如果右子节点为空,当前位置就是适合插入新节点的位置if (root->right == nullptr) return root;// 否则,在右子树中继续查找return findBST(root->right, val);}}// 在二叉搜索树中插入一个新的节点TreeNode* insertIntoBST(TreeNode* root, int val) {// 创建新节点TreeNode* newnode = new TreeNode(val);// 如果树为空,新节点即为根节点if (root == nullptr) {return newnode;}// 查找适合插入新节点的位置,并得到该位置的父节点TreeNode* parent = findBST(root, val);// 根据val的值决定新节点是作为左子节点还是右子节点if (val < parent->val) {parent->left = newnode;} else {parent->right = newnode;}// 返回根节点return root;}
};

算法的时间复杂度为O(logn)(二叉搜索树,最差为O(n)),空间复杂度为O(1)。

删除二叉搜索树中的节点

有五种情况

1.未找到需要删除的节点

2.删除的是叶节点

3.删除的节点仅有右子树

4.删除的节点仅有左子树

5.删除的节点左右子树都在

针对这五种情况,有以下五种解答方案

1.直接返回二叉搜索树的根节点

2.直接删除即可

3.将右孩子代替被删除的节点

4.将左孩子代替被删除的节点

5.有两种解决方式,分别是让被删除节点的右孩子或左孩子即位,以右孩子即位,查找右子树下的最小值节点,将节点的左子树全部接入该节点,或以左孩子即位,查找左子树下的最大值节点,将节点的右子树全部接入该节点。

class Solution {
public:TreeNode* find_parent(TreeNode* root, int key) {if (root == nullptr || (root->left == nullptr && root->right == nullptr)) {return nullptr; // 如果当前节点为空或为叶节点,返回nullptr}if (root->left != nullptr && root->left->val == key) {return root; // 如果左子节点的值等于key,返回当前节点作为父节点}if (root->right != nullptr && root->right->val == key) {return root; // 如果右子节点的值等于key,返回当前节点作为父节点}if (key < root->val) {return find_parent(root->left, key); // 如果key小于当前节点的值,递归地在左子树中查找} else {return find_parent(root->right, key); // 如果key大于或等于当前节点的值,递归地在右子树中查找}}TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return nullptr;if (root->val == key) {// 要删除的节点是根节点if (root->left == nullptr) return root->right; // 只有右子树if (root->right == nullptr) return root->left; // 只有左子树// 有两个子节点,找到右子树的最小节点TreeNode* minNode = getMin(root->right);root->val = minNode->val; // 将右子树的最小节点的值赋给当前节点root->right = deleteNode(root->right, minNode->val); // 删除右子树中的最小节点} else if (key < root->val) {root->left = deleteNode(root->left, key); // 在左子树中递归删除} else {root->right = deleteNode(root->right, key); // 在右子树中递归删除}return root;}TreeNode* getMin(TreeNode* node) {while (node->left != nullptr) node = node->left;return node;}
};

算法的时间复杂度需要考虑树的高度,查找树中要删除的节点,需要O(logn)的时间,当需要删除的节点有两个子节点时,需要找到右子树中的最小节点,这同样需要O(logn)的时间,最坏情况下时间复杂度为O(logn)。

空间复杂度主要取决于递归栈的深度,因此,空间复杂度也为O(logn)。

这篇关于代码随想录算法训练营Day22|235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1015681

相关文章

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

Python 中的 with open文件操作的最佳实践

《Python中的withopen文件操作的最佳实践》在Python中,withopen()提供了一个简洁而安全的方式来处理文件操作,它不仅能确保文件在操作完成后自动关闭,还能处理文件操作中的异... 目录什么是 with open()?为什么使用 with open()?使用 with open() 进行

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

Linux ls命令操作详解

《Linuxls命令操作详解》通过ls命令,我们可以查看指定目录下的文件和子目录,并结合不同的选项获取详细的文件信息,如权限、大小、修改时间等,:本文主要介绍Linuxls命令详解,需要的朋友可... 目录1. 命令简介2. 命令的基本语法和用法2.1 语法格式2.2 使用示例2.2.1 列出当前目录下的文

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.