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

【每日一题Day222】LC1110删点成林 | dfs后序

删点成林【LC1110】

给出二叉树的根节点 root,树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现,我们就把该节点从树上删去,最后得到一个森林(一些不相交的树构成的集合)。

返回森林中的每棵树。你可以按任意顺序组织答案。

又是一段瓶颈期
2023/5/30

  • 思路

    遍历树时,如果当前节点需要删除,那么其孩子节点如果存在的话,那么就变成了单独的树,需要单独添加至结构集中。

    • 因此,可以使用哈希表记录 to_delete 中的值,快速判断某个节点是否需要删除
    • 然后后序遍历该树,先将左右子树中需要删除的节点删除,然后判断父节点是否需要删除
      • 如果需要删除时如果左右孩子不为空,将其放入结果集中;
      • 如果父节点不需要删除,七左右子树中某些节点可能已经被删除,那么更新其左右孩子
    • 最后判断根节点是否被删除,如果未被删除,那么将其放入结果集中(也可以设置假的根节点,避免重复代码)
  • 实现

    /*** 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 Solution {// 后序 如果根节点要删除,那么把左右节点放入结果集中Set<Integer> del;List<TreeNode> res;public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {this.del = new HashSet<>();this.res = new ArrayList<>();for (int d : to_delete){del.add(d);}TreeNode newRoot = dfs(root);if (newRoot != null){res.add(newRoot);}return res;}public TreeNode dfs(TreeNode node){if (node == null){return null;}node.left = dfs(node.left);node.right = dfs(node.right);if (del.contains(node.val)){// 删除当前节点           // 如果孩子节点不为空,加入结果集中if (node.left != null){res.add(node.left);}if (node.right != null){res.add(node.right);}node = null;}return node;}
    }
    
    • 复杂度
      • 时间复杂度: O ( n + m ) \mathcal{O}(n+m) O(n+m) n n n为二叉树的节点数目, m m mto_delete的长度
      • 空间复杂度: O ( n + m ) \mathcal{O}(n+m) O(n+m)

相关文章:

【每日一题Day222】LC1110删点成林 | dfs后序

删点成林【LC1110】 给出二叉树的根节点 root&#xff0c;树上每个节点都有一个不同的值。 如果节点值在 to_delete 中出现&#xff0c;我们就把该节点从树上删去&#xff0c;最后得到一个森林&#xff08;一些不相交的树构成的集合&#xff09;。 返回森林中的每棵树。你可以按…...

[ChatGPT] 从 GPT-3.5 到 GPT-5 的进化之路 | ChatGPT和程序员 : 协作 or 取代

⭐作者介绍&#xff1a;大二本科网络工程专业在读&#xff0c;持续学习Java&#xff0c;努力输出优质文章 ⭐作者主页&#xff1a;逐梦苍穹 ⭐如果觉得文章写的不错&#xff0c;欢迎点个关注一键三连&#x1f609;有写的不好的地方也欢迎指正&#xff0c;一同进步&#x1f601;…...

6.4 GDP调试多进程程序

目录 GDB调试多进程程序 安装gdb gdb编译 运行gdb 单步运行 从头到尾运行 下一步 运行子进程 同时运行父进程 查看运行的进程 切换进程 退出 GDB调试多进程程序 set follow-fork-mode child 设置GDB调试子进程 set follow-fork-mode parent 设置GDB调试父进…...

TDengine 时序数据的保留策略

“TDengine除vnode分片之外&#xff0c;还对时序数据按照时间段进行分区。每个数据文件只包含一个时间段的时序数据&#xff0c;时间段的长度由DB的配置参数days决定。这种按时间段分区的方法还便于高效实现数据的保留策略&#xff0c;只要数据文件超过规定的天数&#xff08;系…...

Java-多线程解析1

一、线程的描述&#xff1a; 1、线程是一个应用程序进程中不同的执行路径比例如&#xff1a;一个WEB服务器&#xff0c;能够为多个用户同时提供请求服务&#xff1b;而 -> 进程是操作系统中正在执行的不同的应用程序,比如&#xff1a;我们可以同时打开系统的word和游戏 2、多…...

PHP 判断用户当前坐标是否在电子围栏内

可以使用射线法判断用户当前坐标点是否在电子围栏内。 具体步骤如下&#xff1a; 1. 将电子围栏的四个角坐标按顺序连接成一个封闭多边形。 2. 从用户当前坐标点向外发射一条射线&#xff0c;判断这条射线与多边形的交点个数。 3. 如果交点个数为奇数&#xff0c;则用户当前…...

Java版本工程管理系统源码企业工程项目管理系统简介

一、立项管理 1、招标立项申请 功能点&#xff1a;招标类项目立项申请入口&#xff0c;用户可以保存为草稿&#xff0c;提交。 2、非招标立项申请 功能点&#xff1a;非招标立项申请入口、用户可以保存为草稿、提交。 3、采购立项列表 功能点&#xff1a;对草稿进行编辑&#x…...

高速缓存(cache)的原理: 了解计算机架构与性能优化

计基之存储器层次结构 Author&#xff1a; Once Day Date&#xff1a; 2023年5月9日 长路漫漫&#xff0c;而今才刚刚启程&#xff01; 本内容收集整理于《深入理解计算机系统》一书。 参看文档: 捋一捋Cache - 知乎 (zhihu.com)iCache和dCache一致性 - 知乎 (zhihu.com)C…...

【Vue3+TS项目】硅谷甄选day04--顶部组件搭建+面包屑+路由鉴权

顶部组件搭建 顶部左侧折叠和面包屑实现 左侧菜单刷新折叠的问题解决---属性default-active 折叠之后图标不见&#xff1a;icon放在插槽外面----element的menu属性&#xff1a;collapse project\src\layout\index.vue // 获取路由对象 import { useRoute } from vue-route…...

某oa 11.10 未授权任意文件上传

漏洞简介 之前也对通达 oa 做过比较具体的分析和漏洞挖掘&#xff0c;前几天看到通达 oa 11.10 存在未授权任意文件上传漏洞&#xff0c;于是也打算对此进行复现和分析。 环境搭建 https://www.tongda2000.com/download/p2019.php 下载地址 &#xff1a;https://cdndown.tongda…...

Grounded Language-Image Pre-training(论文翻译)

文章目录 Grounded Language-Image Pre-training摘要1.介绍2.相关工作3.方法3.1统一构建3.2.语言感知深度融合3.3.使用可扩展的语义丰富数据进行预训练 4.迁移到既定的基准4.1.COCO上的zero-shot和监督迁移学习4.2.LVIS上的zero-shot 迁移学习4.3.Flickr30K实体上的 phrase gro…...

设计模式-行为型模式(模板方法、策略、观察者、迭代器、责任链、命令、状态、备忘录、访问者、中介者、解释器)

行为型模式&#xff1a;专注于对象之间的 协作 及如何通过彼此之间的交互来完成任务。行为型模式通常集中在描述对象之间的 责任 分配和 通信 机制&#xff0c;并提供了一些优雅解决特定问题的方案。 模板方法模式(Template Method Pattern)策略模式(Strategy Pattern)观察者模…...

全面探讨 Spring Boot 的自动装配机制

Spring Boot 是一个基于 Spring 框架的快速开发脚手架&#xff0c;它通过自动配置机制帮助我们快速搭建应用程序&#xff0c;从而减少了我们的配置量和开发成本。自动装配是 Spring Boot 的核心特点之一&#xff0c;它可以减少项目的依赖&#xff0c;简化配置文件&#xff0c;提…...

河道水位监测:河道水位监测用什么设备

中国地形复杂&#xff0c;气候多样&#xff0c;导致水资源分布不均&#xff0c;洪涝和干旱等问题时有发生。同时&#xff0c;人类活动也对水资源造成了很大压力&#xff0c;工业和农业用水增加&#xff0c;河道水位下降&#xff0c;生态环境受到威胁。因此&#xff0c;对河道水…...

嵌入式系统中u-boot和bootloader到底有什么区别

嵌入式软件工程师都听说过 u-boot 和 bootloader&#xff0c;但很多工程师依然不知道他们到底是啥。 今天就来简单讲讲 u-boot 和 bootloader 的内容以及区别。 Bootloader Bootloader从字面上来看就是启动加载的意思。用过电脑的都知道&#xff0c;windows开机时会首先加载…...

实验14:20211030 1+X 中级实操考试(id:2498)

实验14&#xff1a;20211030 1X 中级实操考试&#xff08;id&#xff1a;2498&#xff09; 一、项目背景说明二、表结构三、步骤【5 分】步骤 1&#xff1a;项目准备【5 分】步骤 2&#xff1a;完成实体类 Member【10 分】步骤 3&#xff1a;完成实体类 Goods【10 分】步骤 4&a…...

(字符串 ) 剑指 Offer 58 - II. 左旋转字符串 ——【Leetcode每日一题】

❓剑指 Offer 58 - II. 左旋转字符串 难度&#xff1a;简单 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如&#xff0c;输入字符串"abcdefg"和数字2&#xff0c;该函数将返回左旋转两位得到的…...

EPICS编程

提纲 1&#xff09; 为什么在EPICS上编程 2&#xff09;构建系统特性&#xff1a;假设基本理解Unix Make 3&#xff09;在libCom中可用的工具 1&#xff09; 为什么在EPICS上编程 1、社区标准&#xff1a;EPICS合作者知道和明白EPICS结构 2、在很多操作系统之间代码移值性…...

17:00面试,还没10分钟就出来了,问的实在是太...

从外包出来&#xff0c;没想到死在另一家厂子 自从加入这家公司&#xff0c;每天都在加班&#xff0c;钱倒是给的不少&#xff0c;所以也就忍了。没想到8月一纸通知&#xff0c;所有人不许加班&#xff0c;薪资直降30%&#xff0c;顿时有吃不起饭的赶脚。 好在有个兄弟内推我去…...

docker都有那些工具,及工具面试题

docker介绍 Docker 是一种开源的容器化平台&#xff0c;可以帮助开发者将应用程序和依赖项打包到轻量级的容器中&#xff0c;然后部署到任何基于 Linux 的操作系统中。使用 Docker 可以大大简化开发、部署和管理应用程序的过程&#xff0c;使其更加快速、灵活和可靠。 Docker…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...