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

    // 查找是否包含target
    public 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为树的节点数,空间复杂度主要为哈希表占用的空间。

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

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于pci多功能采集卡——pci9640

一、追逐潮流&#xff0c;应运而生 信息社会的高速发展&#xff0c;在很大程度上取决于信息与信号处理的先进性。数字信号处理技术的出现改变了信号与信号处理技术的整个面貌&#xff0c;而数据采集作为数字信号处理的必不可少的前期工作在整个数字系统中起到关键性乃至决定性的…

C# RAM Stable Diffusion 提示词反推 Onnx Demo

目录 介绍 效果 模型信息 项目 代码 下载 C# RAM Stable Diffusion 提示词反推 Onnx Demo 介绍 github地址&#xff1a;GitHub - xinyu1205/recognize-anything: Open-source and strong foundation image recognition models. Open-source and strong foundation ima…

【Android】源码中的建造者模式

本文是基于 Android 14 的源码解析 在 Android 源码中&#xff0c;最常用到的建造者模式就是 AlertDialog.Builder&#xff0c;使用该建造者来构建复杂的 AlertDialog 对象。在开发过程中&#xff0c;我们经常用到 AlertDialog&#xff0c;具体示例如下&#xff1a; private f…

SA3D:基于 NeRF 的三维场景分割方法

Paper: Cen J, Zhou Z, Fang J, et al. Segment anything in 3d with nerfs[J]. Advances in Neural Information Processing Systems, 2024, 36. Introduction: https://jumpat.github.io/SA3D/ Code: https://github.com/Jumpat/SegmentAnythingin3D SA3D 是一种用于 NeRF 表…

RabbitMQ 面试题及答案整理,最新面试题

RabbitMQ的核心组件有哪些&#xff1f; RabbitMQ的核心组件包括&#xff1a; 1、生产者&#xff08;Producer&#xff09;&#xff1a; 生产者是发送消息到RabbitMQ的应用程序。 2、消费者&#xff08;Consumer&#xff09;&#xff1a; 消费者是接收RabbitMQ消息的应用程序…

阿里云领盲盒活动

阿里云每次的活动都很给力&#xff0c;实打实地发东西。 这次是体验 通义灵码 的活动&#xff0c;这个是体验的推广链接 「通义灵码 体验 AI 编码&#xff0c;开 AI 盲盒」 我是在vscode安装的&#xff0c;体验还行&#xff0c;抽奖抽到了马克杯 这个是抽奖的具体步骤 https:…

mysql对索引的选择简述

概述 在业务中经常会优化一些mysql的慢查询&#xff0c;通常都是使用explain去查看分析&#xff0c;检查扫描行数和索引的命中情况&#xff1b; 但是在具体索引的选择上&#xff0c;explain结果中并没有直接展示出来&#xff1b; 此时可以开启mysql的追踪优化器Trace功能&…

【Greenhills】MULTI IDE网络版license统计授权使用情况

【更多软件使用问题请点击亿道电子官方网站查询】 1、 文档目标 用于购买了GHS网络版的客户&#xff0c;对于license的调用情况进行统计和管理 2、 问题场景 对于购买了GHS网络版license的客户&#xff0c;想要对于授权的使用情况进行分析和管理&#xff0c;但是&#xff0c;…

c++ 常用函数 集锦 整理中

c 常用函数集锦 目录 1、string和wstring之间转换 1、string和wstring之间转换 std::string convertWStringToString(std::wstring wstr) {std::string str;if (!wstr.empty()){std::wstring_convert<std::codecvt_utf8<wchar_t>> converter;str converter.to_b…

【论文阅读】ACM MM 2023 PatchBackdoor:不修改模型的深度神经网络后门攻击

文章目录 一.论文信息二.论文内容1.摘要2.引言3.作者贡献4.主要图表5.结论 一.论文信息 论文题目&#xff1a; PatchBackdoor: Backdoor Attack against Deep Neural Networks without Model Modification&#xff08;PatchBackdoor:不修改模型的深度神经网络后门攻击&#xf…

西井科技参与IATA全球货运大会 以AI绿动能引领智慧空港新未来

3月12日至14日&#xff0c;由国际航空运输协会IATA主办的全球货运大会&#xff08;World Cargo Symposium&#xff09;在中国香港成功举办&#xff0c;这是全球航空货运领域最大规模与影响力的年度盛会。作为大物流领域全球领先的“智能化与新能源化”综合解决方案提供商&#…

参加大广赛是否有价值?让我们来看答案!

大广赛全称是全国大学生广告艺术大赛&#xff0c;是中国最大的高校广告创意竞赛活动。它由教育部高等教育司指导&#xff0c;中国传媒大学、大广赛文化传播&#xff08;北京&#xff09;有限公司共同举办。 命题素材在线预览https://js.design/f/Jspbti?sourcesh&planbtt…

互联网操作系统Puter

什么是 Puter &#xff1f; Puter 是一个先进的开源桌面环境&#xff0c;运行在浏览器中&#xff0c;旨在具备丰富的功能、异常快速和高度可扩展性。它可以用于构建远程桌面环境&#xff0c;也可以作为云存储服务、远程服务器、Web 托管平台等的界面。Puter 是一个隐私至上的个…

垃圾清理软件大全免费 磁盘空间不足?注册表不敢乱动怎么办?ccleaner官方下载

在日常的工作中&#xff0c;面对重要文件时往往都会备份一份&#xff1b;在下载文件时&#xff0c;有时也会不小心把一份文件下载好多次。这些情况会导致电脑中出现重复的文件&#xff0c;删除这些重复文件&#xff0c;可以节省电脑空间&#xff0c;帮助提高电脑运行速度。那么…

websocket 使用示例

websocket 使用示例 前言html中使用vue3中使用1、安装websocket依赖2、代码 vue2中使用1、安装websocket依赖2、代码 前言 即时通讯webSocket 的使用 html中使用 以下是一个简单的 HTML 页面示例&#xff0c;它连接到 WebSocket 服务器并包含一个文本框、一个发送按钮以及 …

大语言模型RAG-技术概览 (一)

大语言模型RAG-技术概览 (一) 一 RAG概览 检索增强生成&#xff08;Retrieval-AugmentedGeneration, RAG&#xff09;。即大模型在回答问题或生成问题时会先从大量的文档中检索相关的信息&#xff0c;然后基于这些信息进行回答。RAG很好的弥补了传统搜索方法和大模型两类技术…

自然语言处理(NLP)—— 语义关系提取

语义关系是指名词或名词短语之间的联系。这些关系可以是表面形式&#xff08;名词性实体&#xff09;之间的联系&#xff0c;也可以是知识工程中概念之间的联系。在自然语言处理&#xff08;NLP&#xff09;和文本挖掘领域&#xff0c;识别和理解这些语义关系对于信息提取、知识…

[媒体宣传]上海有哪些可以邀约的新闻媒体资源汇总

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 上海作为中国最大的城市之一&#xff0c;拥有丰富的新闻媒体资源。以下是一些可以邀约的新闻媒体资源汇总&#xff1a; 报纸媒体&#xff1a; 《新民晚报》&#xff1a;上海最具影响力…

C#,红黑树(Red-Black Tree)的构造,插入、删除及修复、查找的算法与源代码

1 红黑树(Red-Black Tree) 如果二叉搜索树满足以下红黑属性,则它是红黑树: 每个节点不是红色就是黑色。根是黑色的。每片叶子(无)都是黑色的。如果一个节点是红色的,那么它的两个子节点都是黑色的。对于每个节点,从节点到后代叶的所有路径都包含相同数量的黑色节点。红…

Linux进程概念(2)

一、进程状态 Linux的进程状态实际上就是 struct task_struct 结构体中的一个变量 1.1状态汇总 其中&#xff0c;Linux 状态是用数组储存的&#xff0c;如下&#xff1a; static const char * const task_state_array[] { "R (running)", // 0 …
最新文章