力扣每日一题 在受污染的二叉树中查找元素 哈希 DFS 二进制

Problem: 1261. 在受污染的二叉树中查找元素在这里插入图片描述

思路

👨‍🏫 灵神题解

💖 二进制

  • 时间复杂度:初始化为 O ( 1 ) O(1) O(1);find 为 O ( m i n ( h , l o g 2 t a r g e t ) O(min(h,log_2target) O(min(h,log2target),其中 h 为二叉树的高度
  • 空间复杂度: O ( 1 ) O(1) O(1)
class FindElements {
    private TreeNode root;

    public FindElements(TreeNode root) {
        this.root = root;
    }

    public boolean find(int target) {
        target++;
        TreeNode cur = root; // 从根节点出发
        for (int i = 30 - Integer.numberOfLeadingZeros(target); i >= 0; i--) { // 从次高位开始枚举
            int bit = (target >> i) & 1; // target 第 i 位的比特值
            cur = bit == 0 ? cur.left : cur.right;
            if (cur == null) { // 走到空节点,说明 target 不在二叉树中
                return false;
            }
        }
        return true; // 没有走到空节点,说明 target 在二叉树中
    }
}

在这里插入图片描述

💖 哈希表

复杂度分析

  • 时间复杂度:初始化为 O ( n ) O(n) O(n),其中 n n n 为二叉树的节点个数。find 为 O ( 1 ) O(1) O(1)
  • 空间复杂度: O ( n ) O(n) O(n)
class FindElements {
    private final Set<Integer> s = new HashSet<>();

    public FindElements(TreeNode root) {
        dfs(root, 0);
    }

    public boolean find(int target) {
        return s.contains(target);
    }

    private void dfs(TreeNode node, int val) {
        if (node == null) {
            return;
        }
        s.add(val);
        dfs(node.left, val * 2 + 1);
        dfs(node.right, val * 2 + 2);
    }
}

💖 暴力版

  • 时间复杂度:
    • 转换: O ( n ) O(n) O(n)
    • 查找: O ( n m ) O(nm) O(nm)
  • 空间复杂度: O ( n ) O(n) O(n)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class FindElements {
    TreeNode r;
    public FindElements(TreeNode root) {
        r = root;
        if(root == null) return;
        root.val = 0;
        dfs(root);
    }

    void dfs(TreeNode cur)
    {
        if(cur == null)
            return;
        if(cur.left != null)
        {
            cur.left.val = cur.val * 2 + 1;
            dfs(cur.left);
        }
        if(cur.right != null)
        {
            cur.right.val = cur.val * 2 + 2;
            dfs(cur.right);
        }
    }
    
    boolean f(TreeNode cur, int x)
    {
        if(cur == null)
            return false;
        if(cur.val == x)
            return true;
        if(f(cur.left,x) || f(cur.right,x))
            return true;
        return false;
    }

    public boolean find(int target) {
        return f(r,target);
    }
}

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements obj = new FindElements(root);
 * boolean param_1 = obj.find(target);
 */

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

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

相关文章

Django 学习笔记(Day1)

「写在前面」 本文为千锋教育 Django 教程的学习笔记。本着自己学习、分享他人的态度&#xff0c;分享学习笔记&#xff0c;希望能对大家有所帮助。 目录 0 课程介绍 1 Django 快速入门 1.1 Django 介绍 1.2 Django 安装 1.3 创建 Django 项目 1.4 运行 Django 项目 1.5 数据迁…

【C#】.net core 6.0 使用第三方日志插件Log4net,日志输出到控制台或者文本文档

欢迎来到《小5讲堂》 大家好&#xff0c;我是全栈小5。 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对知识点的理解和掌握。…

【C++】stack/queue

链表完了之后就是我们的栈和队列了&#xff0c;当然我们的STL中也有实现&#xff0c;下面我们先来看一下简单用法&#xff0c;跟我们之前C语言实现的一样&#xff0c;stack和queue有这么几个重要的成员函数 最主要的就是这么几个&#xff1a;empty&#xff0c;push&#xff0c;…

python读取大型csv文件,降低内存占用,提高程序处理速度

文章目录 简介读取前多少行读取属性列逐块读取整个文件总结参考资料 简介 遇到大型的csv文件时&#xff0c;pandas会把该文件全部加载进内存&#xff0c;从而导致程序运行速度变慢。 本文提供了批量读取csv文件、读取属性列的方法&#xff0c;减轻内存占用情况。 import pand…

git commit --amend

git commit --amend 1. 修改已经输入的commit 1. 修改已经输入的commit 我已经输入了commit fix: 删除无用代码 然后现在表示不准确&#xff0c;然后我通过命令git commit --amend修改commit

鼓楼夜市管理wpf+sqlserver

鼓楼夜市管理系统wpfsqlserver 下载地址:鼓楼夜市管理系统wpfsqlserver 说明文档 运行前附加数据库.mdf&#xff08;或sql生成数据库&#xff09; 主要技术&#xff1a; 基于C#wpf架构和sql server数据库 功能模块&#xff1a; 登录注册 鼓楼夜市管理系统主界面所有店铺信…

企业电子招投标系统源码-从源码到实践:深入了解鸿鹄电子招投标系统与电子招投标

在数字化采购领域&#xff0c;企业需要一个高效、透明和规范的管理系统。通过采用Spring Cloud、Spring Boot2、Mybatis等先进技术&#xff0c;我们打造了全过程数字化采购管理平台。该平台具备内外协同的能力&#xff0c;通过待办消息、招标公告、中标公告和信息发布等功能模块…

Tictoc3例子

在tictoc3中&#xff0c;实现了让 tic 和 toc 这两个简单模块之间传递消息&#xff0c;传递十次后结束仿真。 首先来介绍一下程序中用到的两个函数&#xff1a; 1.omnetpp中获取模块名称的函数 virtual const char *getName() const override {return name ? name : "&q…

Python 一步一步教你用pyglet制作汉诺塔游戏(终篇)

目录 汉诺塔游戏 完整游戏 后期展望 汉诺塔游戏 汉诺塔&#xff08;Tower of Hanoi&#xff09;&#xff0c;是一个源于印度古老传说的益智玩具。这个传说讲述了大梵天创造世界的时候&#xff0c;他做了三根金刚石柱子&#xff0c;并在其中一根柱子上从下往上按照大小顺序摞…

js【详解】Promise

为什么需要使用 Promise &#xff1f; 传统回调函数的代码层层嵌套&#xff0c;形成回调地狱&#xff0c;难以阅读和维护&#xff0c;为了解决回调地狱的问题&#xff0c;诞生了 Promise 什么是 Promise &#xff1f; Promise 是一种异步编程的解决方案&#xff0c;本身是一个构…

套接字的地址结构,IP地址转换函数,网络编程的接口

目录 一、套接字的地址结构 1.1 通用socket地址结构 1.2 专用socket地址结构 1.2.1 tcp协议族 1.2.3 IP协议族 二、IP地址转换函数 三、网络编程接口 3.1 socket() 3.2 bind() 3.3 listen() 3.4 accept() 3.5 connect() 3.6 close() 3.7 recv()、send() 3.8 recv…

手写简易操作系统(五)--获得物理内存容量

前情提要 上一章中我们进入了保护模式&#xff0c;并且跳转到了32位模式下执行。这一章较为简单&#xff0c;我们来获取物理内存的实际容量。 一、获得内存容量的方式 在Linux中有多种方法获取内存容量&#xff0c;如果一种方法失败&#xff0c;就会试用其他方法。其本质上是…

考研数学|汤家凤《1800》vs 张宇《1000》,怎么选?

汤家凤的1800题和张宇的1000题都是备考数学考研的热门选择&#xff0c;但究竟哪个更适合备考呢&#xff1f;下面分享一些见解。 首先&#xff0c;让我们来看看传统习题册存在的一些问题。虽然传统习题册通常会覆盖考试的各个知识点和题型&#xff0c;但其中一些问题在于它们可…

JDBC连接MysqL

import java.sql.*;public class Demo {public static void main(String[] args) throws ClassNotFoundException, SQLException {//1.注册驱动&#xff0c;加载驱动&#xff1b;Class.forName("com.mysql.jdbc.Driver");//2.获得连接,返回connection类型的对象&…

汤唯短发造型:保留经典和适合自己的风格,也许才是最重要的

汤唯短发造型&#xff1a;保留经典和适合自己的风格&#xff0c;也许才是最重要的 汤唯短发造型登上Vogue四月刊封面&#xff0c;引发网友热议。#李秘书讲写作#说说是怎么回事&#xff1f; 这次Vogue四月刊的封面大片&#xff0c;汤唯以一头短发亮相&#xff0c;身穿五颜六色的…

钉钉平台“智”领宠物界,开启萌宠智能新时代!

在当前数字化转型的浪潮中&#xff0c;钉钉用便捷的数字化解决方案推动了宠物业界的智能升级。一家宠物用品公司采用无雀科技数字化管理系统&#xff0c;与钉钉平台结合&#xff0c;解决了小型企业普遍存在的财务管理不清晰、业务流程不规范、客户信息核对繁琐等痛点问题。 针对…

一周学会Django5 Python Web开发-Django5内置模板引擎-模板继承

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计34条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…

Linux中文件的权限

我们首先需要明白&#xff0c;权限 用户角色 文件的权限属性 一、拥有者、所属组和other&#xff08;用户角色&#xff09; 以文件file1为例 第一个箭头所指处即是文件的拥有者&#xff0c;拥有者为zz 第二个箭头所指处即使文件的所属组&#xff0c;所属组为zz 除去拥有者…

嵌入式系统工程师错题总结

笔者来介绍一下嵌入式系统工程师考试的一些易错题目 题目介绍  流水线指令计算公式&#xff1a;一条指令总时间max&#xff08;单个指令执行时间&#xff09;*&#xff08;指令数-1&#xff09;  平均故障间隔时间  ICMP协议&#xff1a;传送通信问题相关的消息。 …

电脑打开应用慢

电脑打开什么应用都很慢 我的电脑是i73060&#xff0c;但是打开应用很慢 解决办法&#xff1a; 在注册表[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\CI\Policy]将"VerifiedAndReputablePolicyState"的值设置为0&#xff0c;如果没有这一项&#xff0c;就…