找工作准备刷题Day8 二叉树 (卡尔41期训练营 7.22)

第一题:Leetcode235. 二叉搜索树的最近公共祖先

题目描述

 题解1——递归法

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;}// p和q一个在左子树,一个在右子树,返回rootreturn root;}
};

要点

  1.  p和q都大于root->val,可以判定,其在root的右子树上;
  2.  p和q都小于root->val,可以判定,其在root的左子树上;
  3. p和q一个在左子树,一个在右子树,返回root。

题解2——迭代法

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

原理同递归法。

第二题:Leetcode701. 二叉搜索树中的插入操作

题目描述

 要点

  1. Node.val值独一无二且在原始BST中不存在(其实这种限制脱离实际,在解题时应该基于更加复杂的环境多思考)
  2. 对于root和val值,如果root->val大于val,取root->left;如果root->val小于val,取root->right
  3. 需要时刻牢记返回值的意义。

题解

class Solution {
public:// 返回插入后树的根节点TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == nullptr) {// 到达插入位置root = new TreeNode(val);return root;}if (root->val > val)root->left = insertIntoBST(root->left, val);elseroot->right = insertIntoBST(root->right, val);return root;}
};

第三题:Leetcode450. 删除二叉搜索树中的节点

题目描述

解题思路

根据二叉搜索树的特性:根节点大于所有左子树节点,根节点小于所有右子树节点。

据此可以写出题解1。

对于普通二叉树,可以写出题解2。

题解1——利用二叉搜索树的特性

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr)return nullptr;if (root->val == key) {// root为叶子节点,delete root并返回nullptrif (root->left == nullptr && root->right == nullptr) {delete root;return nullptr;}// 左子树或者右子树其中一个为nullptr,另一个存在,返回存在的,并删除rootif (root->left == nullptr || root->right == nullptr) {TreeNode* returnNode =root->left == nullptr ? root->right : root->left;delete root;return returnNode;}// 左右子树都存在,将左子树 设置为 右子树最左边节点的左儿子if (root->left != nullptr && root->right != nullptr){TreeNode* node = root->right;while(node->left)node = node->left;node->left = root->left;TreeNode* toDelete = root;root = root->right;delete toDelete;return root;}} else if (root->val > key)root->left = deleteNode(root->left, key);elseroot->right = deleteNode(root->right, key);return root;}
};

要点

  1. 当 root 为空时,找不到key,返回 nullptr;
  2. 当 root 取值大于key时,在左子树进行删除,并返回删除后的左子树;
  3. 当 root 取值小于key时,在右子树进行删除,并返回删除后的右子树;
  4. 当 root 取值为key时,存在以下几种情况:

【1】、左子树和右子树均为nullptr,delete root,返回nullptr即可;

【2】、左子树或者右子树其中一个为nullptr时,delete root,返回不为空的子树;

【3】、左右子树均不为空,为了保证删除root后仍为二叉搜索树,可以将左子树设置为右子树最左边节点的左子树(详见代码,下图从卡尔代码网复制过来的)。

题解2——不利用二叉搜索树,通用方法(交换)

解题思路

  1. 找到待删除的节点
  2. 将待删除的节点与其右子树最左侧节点交换,此时待删除节点换到了底层(不一定是叶子节点)
  3. 很绕很绕。。。

代码

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr)return root;if (root->val == key) {// 第二次操作,将已经被调换到最下方的待删除节点删除// 此处,当root的右子树为空,直接返回左子树即可。// 因此,其完成两部分内容:第二次删除 + 处理右子树为空情况。if(root->right == nullptr){return root->left;}// 进入这里,则右子树不为空,左子树有可能为nullptrTreeNode* cur = root->right;while (cur->left)cur = cur->left;swap(cur->val, root->val);//第一次操作,把待删除的值换到右子树最左边节点}root->left = deleteNode(root->left, key);root->right = deleteNode(root->right, key);return root;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1489194.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

【Python】 ValueError: too many values to unpack 解决方案

【Python】 ValueError: too many values to unpack 解决方案 在Python编程中&#xff0c;ValueError: too many values to unpack是一个常见的错误&#xff0c;通常出现在使用解包操作时。本文将深入探讨这个错误的原因、解决思路、解决方法&#xff0c;并通过具体案例帮助大…

DLMS/COSEM中公开密钥算法的使用_椭圆曲线加密法

1.概述 椭圆曲线密码涉及有限域上的椭圆曲线上的算术运算。椭圆曲线可以定义在任何数字域上(实数、整数、复数)&#xff0c;但在密码学中&#xff0c;椭圆曲线最常用于有限素数域。 素数域上的椭圆曲线由一组实数(x, y)组成&#xff0c;满足以下等式: 方程的所有解的集合构成…

fatal: refusing to merge unrelated histories

出现本地仓库和远程仓库的代码合并不兼容问题&#xff0c;解决方法&#xff1a; 添加--allow-unrelated-histories&#xff0c;让git允许提交不关联的历史代码。 成功提交&#xff1a;

Hive3:基本介绍

一、概述 Apache Hive是一款分布式SQL计算的工具&#xff0c; 其主要功能是&#xff1a; 将SQL语句翻译成MapReduce程序运行 Hive是单机工具&#xff0c;只需要部署在一台服务器即可。 Hive虽然是单机的&#xff0c;但是它可以提交分布式运行的MapReduce程序运行。 二、基本…

RocketMQ消息短暂而又精彩的一生(荣耀典藏版)

目录 前言 一、核心概念 二、消息诞生与发送 2.1.路由表 2.2.队列的选择 2.3.其它特殊情况处理 2.3.1.发送异常处理 2.3.2.消息过大的处理 三、消息存储 3.1.如何保证高性能读写 3.1.1.传统IO读写方式 3.2零拷贝 3.2.1.mmap() 3.2.2sendfile() 3.2.3.CommitLog …

22 Python常用内置函数——枚举

enumerate() 函数用来枚举可迭代对象中的元素&#xff0c;返回可迭代的 enumerate 对象&#xff0c;其中每个元素都是包含索引和值的元组。 print(enumerate(abcd)) print(list(enumerate(abcd))) # 枚举字符串中的元素 print(list(enumerate([hello, world]))) # 枚举列表中…

SQL 语句中的字符串有单引号导致报错的解决

1.问题 SQL 语句执行对象中&#xff0c;本内容的字符串内含有单引号导致查询或插入数据库报错&#xff0c; 例如 str 关键字 AND 附近有语法错误 2.解决 字符串中的 ’ → 替换 ”&#xff0c;则查询语句成功&#xff0c;故程式中要备注替换 单引号。

工厂数字化转型,该如何建设数字孪生车间?

在工业4.0的浪潮下&#xff0c;数字化转型已成为工厂升级的必然趋势&#xff0c;而数字孪生技术的引入则为这一转型注入了强大动力。智汇云舟作为数字孪生行业头部企业和视频孪生技术首倡者&#xff0c;以创新的视角和前沿的技术&#xff0c;为数字工业建设助力&#xff0c;给众…

大学计算机专业主要课程及概要介绍

大学计算机专业主要课程及概要介绍 大学计算机专业是一门涵盖广泛领域的学科&#xff0c;旨在培养学生在计算机科学与技术方面的理论知识与实践能力。该专业课程设置丰富多样&#xff0c;涵盖了从基础理论到高级应用的多个方面。以下是一些主要的课程及其概要介绍&#xff1a;…

Spring源码-从源码层面讲FactoryBean接口的使用

一般情况下&#xff0c;Spring通过反射机制利用bean的class属性指定实现类来实例化bean。在某些情况下&#xff0c;实例化bean过程比较复杂&#xff0c;如果按照传统的方式&#xff0c;则需要在标签中提供大量的配置信息&#xff0c;配置方式的灵活性是受限的。为此&#xff0c…

深度解析Linux-C——结构体(初始化,结构体数组,结构体大小,位段操作,联合体,内存对齐,C的预处理,宏和带参宏,条件编译)

目录 结构体的三种初始化 结构体的两种引用 结构体数组 结构体大小 结构体实现位段操作 联合体 内存对齐 C的预处理 带参宏 条件编译 结构体的三种初始化 定义如下结构体 struct student {char name[100]; int age; float height; } ; 1、定义变量时初始化 s…

LeetCode Hot100 将有序数组转换为二叉搜索树

给你一个整数数组 nums &#xff0c;其中元素已经按 升序 排列&#xff0c;请你将其转换为一棵 平衡 二叉搜索树。 示例 1&#xff1a; 输入&#xff1a;nums [-10,-3,0,5,9] 输出&#xff1a;[0,-3,9,-10,null,5] 解释&#xff1a;[0,-10,5,null,-3,null,9] 也将被视为正确…

HAL STM32 SPI/ABZ/PWM方式读取MT6816磁编码器数据

HAL STM32 SPI/ABZ/PWM方式读取MT6816磁编码器数据 &#x1f4da;MT6816相关资料&#xff08;来自商家的相关资料&#xff09;&#xff1a; 资料&#xff1a;https://pan.baidu.com/s/1CAbdLBRi2dmL4D7cFve1XA?pwd8888 提取码&#xff1a;8888&#x1f4cd;驱动代码编写&…

WordPress原创插件:自定义文章标题颜色

插件设置截图 文章编辑时&#xff0c;右边会出现一个标题颜色设置&#xff0c;可以设置为任何颜色 更新记录&#xff1a;从输入颜色css代码&#xff0c;改为颜色选择器&#xff0c;更方便&#xff01; 插件免费下载 https://download.csdn.net/download/huayula/89585192…

排序系列 之 希尔排序

&#xff01;&#xff01;&#xff01;排序仅针对于数组哦本次排序是按照升序来的哦 介绍 英文名为ShellSort&#xff0c;又称“缩小增量排序”是直接插入排序算法的一种更高效的改进版本希尔排序是把记录按下标的指定步长分组&#xff0c;然后按照每组使用直接插入排序&#…

Github 2024-07-26开源项目日报 Top10

根据Github Trendings的统计,今日(2024-07-26统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Java项目2TypeScript项目2C++项目2HTML项目1Python项目1C#项目1Lua项目1JavaScript项目1Vue项目1C项目1免费编程学习平台:freeCodeCamp.org 创…

UDP的报文结构及其注意事项

1. 概述 UDP&#xff08;User Datagram Protocol&#xff09;是一种无连接的传输层协议&#xff0c;它提供了一种简单的数据传输服务&#xff0c;不保证数据的可靠传输。在网络通信中&#xff0c;UDP通常用于一些对实时性要求较高、数据量较小、传输延迟较低的应用&#xff0c…

【cuda】在老服务器上配置CUDA+cmake开发环境

在老服务器上配置CUDA+cmake开发环境 服务器x86_64,系统是centos8,cmake版本是2.8.10 背景 不能更换服务器系统无法下载CUDA安装包解决思路 使用可以至此CUDA开发的较老的cmake直接移植CUDA环境配置环境中遇到的问题 服务器无法编译cmake移植CUDA编译器及部分库,代码无法…

【Golang 面试基础题】每日 5 题(十)

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/UWz06 &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 Golang 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏…

FPGA开发——LED流水灯实现先从左往右流水,再从右往左流水

一、概述 我们在设计完一个方向的流水灯的设计时&#xff0c;总是会想实现让流水灯倒着流水回去的设计&#xff0c;这里我也是一样&#xff0c;实现这种设计的方法有很多种&#xff0c;其中就有直接使用case语句将所有可能包含进去编写&#xff0c;这种设计方法是最简单的&…