当前位置: 首页 > news >正文

LeetCode(力扣)算法题_1261_在受污染的二叉树中查找元素

今天是2024年3月12日,可能是因为今天是植树节的原因,今天的每日一题是二叉树🙏🏻

在受污染的二叉树中查找元素

题目描述 

给出一个满足下述规则的二叉树:

root.val == 0

如果 treeNode.val == x 且 treeNode.left != null,那么 treeNode.left.val == 2 * x + 1

如果 treeNode.val == x 且 treeNode.right != null,那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」,所有的 treeNode.val 都变成了 -1

请你先还原二叉树,然后实现 FindElements 类:

FindElements(TreeNode* root) 用受污染的二叉树初始化对象,你需要先把它还原。

bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

示例 1:

输入:
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
输出:
[null,false,true]
解释:
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True 

示例 2:

输入:
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出:
[null,true,true,false]
解释:
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

示例 3:

输入:
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出:
[null,true,false,false,true]
解释:
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True

解题思路

利用哈希表

还原二叉树

        从 root 出发,先将 root 的 val 还原为 0,再从 root 出发 dfs 这棵树(还原二叉树):

  • 递归左儿子:传入 val⋅2+1。
  • 递归右儿子:传入 val⋅2+2。

        递归的同时,把还原后的节点值加到一个哈希表中。

class FindElements {private Set<Integer> valSet = new HashSet<>();// 还原根节点,并dfs二叉树public FindElements(TreeNode root) {dfs(root, 0);}// 还原二叉树并将val存入哈希表private void dfs(TreeNode node, int val) {if (node == null) {return;}valSet.add(val);dfs(node.left, val * 2 + 1);dfs(node.right, val * 2 + 2);}
}

         再利用哈希表的 contains 方法,查找哈希表中知否包含 target 值。

class FindElements {private Set<Integer> valSet = new HashSet<>();// 还原根节点,并dfs二叉树public FindElements(TreeNode root) {dfs(root, 0);}// 查找是否包含targetpublic boolean find(int target) {return valSet.contains(target);}// 还原二叉树并将val存入哈希表private void dfs(TreeNode node, int val) {if (node == null) {return;}valSet.add(val);dfs(node.left, val * 2 + 1);dfs(node.right, val * 2 + 2);}
}

        到这里这个算法问题就算解决啦,解决这个问题的方法有很多种,我也只是选了一种我自己了解的记录下来,大家可以自己去尝试不同的解法(比如力扣上一位大佬写出了用位运算的二进制解法)。

算法复杂度分析

时间复杂度:

        构造函数的时间复杂度为 O(n),

        函数的时间复杂度为 O(1)。

空间复杂度:O(n)。

        n为树的节点数,空间复杂度主要为哈希表占用的空间。

        写在最后:植树节快乐~天天快乐~多种树~ 

相关文章:

LeetCode(力扣)算法题_1261_在受污染的二叉树中查找元素

今天是2024年3月12日&#xff0c;可能是因为今天是植树节的原因&#xff0c;今天的每日一题是二叉树&#x1f64f;&#x1f3fb; 在受污染的二叉树中查找元素 题目描述 给出一个满足下述规则的二叉树&#xff1a; root.val 0 如果 treeNode.val x 且 treeNode.left ! n…...

Topaz DeNoise AI for Mac/Win:引领图片降噪新纪元,让你的照片焕然一新!

在数字化时代&#xff0c;摄影已成为我们记录生活、表达情感的重要方式。然而&#xff0c;随着摄影技术的不断发展&#xff0c;我们也不得不面对一个令人头疼的问题——图片噪点。无论是低光环境下的拍摄&#xff0c;还是高ISO带来的画质损失&#xff0c;噪点总是如影随形&…...

云计算OpenStack KVM迁移

动态迁移 static migration 静态迁移 cold migration 冷迁移 offline migration 离线迁移 live migration 动态迁移 hot migration 热迁移 online migration 在线迁移 衡量 整体迁移时间 服务器停机时间 性能影响(迁移后和其它客户机) 特点 负载均衡 解除硬件依赖…...

【漏洞复现】网康科技 NS-ASG 应用安全网关 SQL注入漏洞(CVE-2024-2330)

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…...

2024年华为OD机试真题-查找众数及中位数-Java-OD统一考试(C卷)

题目描述: 众数是指一组数据中出现次数量多的那个数,众数可以是多个。 中位数是指把一组数据从小到大排列,最中间的那个数,如果这组数据的个数是奇数,那最中间那个就是中位数,如果这组数据的个数为偶数,那就把中间的两个数之和除以2,所得的结果就是中位数。 查找整型数…...

力扣思路题:重复的子字符串

注意比较j与j-i是否相同 bool repeatedSubstringPattern(char* s) {int i;int nstrlen(s);bool flag;for(int i1;i<n/2;i){if(n%i0){flagtrue;}for(int ji;j<n;j){if(s[j]!s[j-i]){flagfalse;break;}}if(flagtrue){return true;}}return false; }...

同城即配年度观察:顺丰同城率先全年盈利,行业破局迎参考

即时消费趋势增强&#xff0c;“万物到家即时可得”成为了消费新常态。这创造出不可忽视的场景潜力&#xff0c;也在无形中让龙头企业的发展质量走到突破点。 3月11日晚&#xff0c;“第三方即时配送第一股”顺丰同城发布公告称&#xff0c;预期实现2023年全年盈利&#xff0c…...

线上机器 swap 过高导致告警

哈喽大家好&#xff0c;我是咸鱼。 今天收到了一个告警&#xff0c;说有台服务器上的 swap 过高&#xff0c;已经用了 50% 以上了。 登录机器查看一下内存以及 swap 的使用情况。 [rootlocalhost ~]# free -h total used free shared buff/cache ava…...

案例分析篇13:系统分析与设计考点(2024年软考高级系统架构设计师冲刺知识点总结系列文章)

专栏系列文章推荐: 2024高级系统架构设计师备考资料(高频考点&真题&经验)https://blog.csdn.net/seeker1994/category_12593400.html 【历年案例分析真题考点汇总】与【专栏文章案例分析高频考点目录】(2024年软考高级系统架构设计师冲刺知识点总结-案例分析篇-…...

算法(结合算法图解)

算法简介简单查找二分查找法 选择排序内存的工作原理数组和链表数组选择排序小结 递归小梗 要想学会递归&#xff0c;首先要学会递归。 递归的基线条件和递归条件递归和栈小结 快速排序分而治之快速排序合并排序时间复杂度的平均情况和最糟情况小结 散列表散列函数缓冲小结性能…...

Linux-多线程

目录 线程概念线程控制创建退出等待join实例detach实例 实例 线程安全概念互斥同步生产者与消费者模型实例 信号量 线程应用 线程概念 线程概念&#xff1a; 有一个零件加工工厂&#xff0c;工厂中有一个或多个工人 工人是干活的&#xff0c;工厂是集体设备资源的载体 进程就是…...

深入解析C++树形关联式容器:map、set及其衍生容器的使用与原理

文章目录 一、引言二、关联式容器的中的 paira.pair 的创建及使用b.pair 间的比较 三、 map 与 set 详解1. map 的基本操作2. set 的基本操作3.关联式容器的迭代器 四、 multimap 与 multiset 的特性五、关联式容器的使用技巧与注意事项1. 键值类型的选择与设计2. 自定义比较函…...

c++基础知识(一)

C字符集&#xff1a;通常将一个标准中能够表示所有字符的一个集合称为字符集。例如Unicode字符集、ASCll、GB2312、BIG5&#xff08;繁体中文及其相关字符&#xff09;等。 字符集是组成程序设计语言的基本要素。由单字符、关键字、标识符、运算符&#xff08;操作符&#xff…...

Midjourney绘图欣赏系列【人物篇】(一)

Midjourney介绍 Midjourney 是生成式人工智能的一个很好的例子&#xff0c;它根据文本提示创建图像。它与 Dall-E 和 Stable Diffusion 一起成为最流行的 AI 艺术创作工具之一。与竞争对手不同&#xff0c;Midjourney 是自筹资金且闭源的&#xff0c;因此确切了解其幕后内容尚不…...

2024 年 2 月 NFT 行业动态:加密货币飙升,NFT 市场调整

作者&#xff1a;stellafootprint.network 数据来源&#xff1a;NFT 研究页面 - Footprint Analytics 2024 年 2 月&#xff0c;加密货币与 NFT 市场显现出了复杂性。该月&#xff0c;NFT 领域的交易量达到 12 亿美元&#xff0c;环比下降了 3.7%。值得关注的是&#xff0c;包…...

【C++那些事儿】深入理解C++类与对象:从概念到实践(下)| 再谈构造函数(初始化列表)| explicit关键字 | static成员 | 友元

&#x1f4f7; 江池俊&#xff1a;个人主页 &#x1f525; 个人专栏&#xff1a;✅C那些事儿 ✅Linux技术宝典 &#x1f305; 此去关山万里&#xff0c;定不负云起之望 文章目录 1. 再谈构造函数1.1 构造函数体赋值1.2 初始化列表1.3 explicit 关键字 2. static成员2.1 概念…...

前端面试 ===> 【Vue2】

Vue2 相关面试题总结 1. 谈谈对Vue的理解 Vue是一种用于构建用户页面的渐进式JavaScript框架&#xff0c;也是一个创建SPA单页面应用的Web应用框架&#xff0c;Vue的核心是 数据驱动试图&#xff0c;通过组件内特定的方法实现视图和模型的交互&#xff1b;特性&#xff1a;&a…...

面试 Java 并发编程八股文十问十答第四期

面试 Java 并发编程八股文十问十答第四期 作者&#xff1a;程序员小白条&#xff0c;个人博客 相信看了本文后&#xff0c;对你的面试是有一定帮助的&#xff01;关注专栏后就能收到持续更新&#xff01; ⭐点赞⭐收藏⭐不迷路&#xff01;⭐ 1&#xff09;Java 中你怎样唤醒…...

物体检测-系列教程27:YOLOV5 源码解析17(训练脚本解读:训练函数4)

&#x1f60e;&#x1f60e;&#x1f60e;物体检测-系列教程 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在Pycharm中进行 本篇文章配套的代码资源已经上传 点我下载源码 24、epoch循环训练------更新、评估、保存 这部分是训练过程的每个epoch结束之前执行的一…...

基于51单片机的数字时钟(万年历)设计与实现

基于51单片机的数字时钟&#xff08;万年历&#xff09;设计与实现 摘要 随着科技的不断发展&#xff0c;数字时钟已成为人们日常生活中不可或缺的一部分。基于51单片机的数字时钟&#xff08;万年历&#xff09;设计&#xff0c;结合了传统时钟的功能与现代电子技术&#xf…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决

问题&#xff1a; pgsql数据库通过备份数据库文件进行还原时&#xff0c;如果表中有自增序列&#xff0c;还原后可能会出现重复的序列&#xff0c;此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”&#xff0c;…...

Linux-进程间的通信

1、IPC&#xff1a; Inter Process Communication&#xff08;进程间通信&#xff09;&#xff1a; 由于每个进程在操作系统中有独立的地址空间&#xff0c;它们不能像线程那样直接访问彼此的内存&#xff0c;所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...