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

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

题目链接:235. 二叉搜索树的最近公共祖先 - 力扣(LeetCode)

class Solution
{
public:TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q){if(root==nullptr||root==p||root==q) return root;TreeNode *left=lowestCommonAncestor(root->left,p,q);TreeNode *right=lowestCommonAncestor(root->right,p,q);if(left&&right) return root;else if(left&&!right) return left;else if(!left&&right) return right;else return nullptr;}
};

偷懒了,用昨天学的二叉树寻找最近公共祖先的方式做了。并没有考虑有二叉搜索树带来的便捷。

题目链接:701. 二叉搜索树中的插入操作 - 力扣(LeetCode)

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

利用二叉搜索树的特性,大的放右,小的放左,碰到空就放下就行。

题目链接:450. 删除二叉搜索树中的节点 - 力扣(LeetCode)

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的右孩子作为新rootdelete 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;}
};

最后还是看了答案。比较难理清,特别是第五种情况。

情况二:找到要删除的节点,左右都为空,直接删除就行,记得返回空指针。

情况三,四:左右孩子有一个不为空的,删除节点,孩子补位,返回补位的节点。

情况五:左右孩子都不为空,这时候就要把左孩子和左孩子的全部孩子都移到  右孩子的 左孩子的左边。(因为是二叉树,所以移动父节点就能把他所有孩子节点移动)。(很绕的情况,但是想一想还是能理解。)最后把右孩子赋给这个节点,删除节点。

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



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

相关文章

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

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

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

《SpringBoot操作MaxComputer方式(保姆级教程)》:本文主要介绍SpringBoot操作MaxComputer方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的... 目录引言uqNqjoe一、引入依赖二、配置文件 application.properties(信息用自己

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

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

HTML5 data-*自定义数据属性的示例代码

《HTML5data-*自定义数据属性的示例代码》HTML5的自定义数据属性(data-*)提供了一种标准化的方法在HTML元素上存储额外信息,可以通过JavaScript访问、修改和在CSS中使用... 目录引言基本概念使用自定义数据属性1. 在 html 中定义2. 通过 JavaScript 访问3.

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

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

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

Flutter监听当前页面可见与隐藏状态的代码详解

《Flutter监听当前页面可见与隐藏状态的代码详解》文章介绍了如何在Flutter中使用路由观察者来监听应用进入前台或后台状态以及页面的显示和隐藏,并通过代码示例讲解的非常详细,需要的朋友可以参考下... flutter 可以监听 app 进入前台还是后台状态,也可以监听当http://www.cppcn

Python使用PIL库将PNG图片转换为ICO图标的示例代码

《Python使用PIL库将PNG图片转换为ICO图标的示例代码》在软件开发和网站设计中,ICO图标是一种常用的图像格式,特别适用于应用程序图标、网页收藏夹图标等场景,本文将介绍如何使用Python的... 目录引言准备工作代码解析实践操作结果展示结语引言在软件开发和网站设计中,ICO图标是一种常用的图像

C#中的 Dictionary常用操作

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