1110. 删点成林

DFS

1110. 删点成林

关键要点

  • 通过O(1)时间复杂度确认节点是否需要删除

Set to_deleteSet = new HashSet<>(); Arrays.stream(to_delete).forEach(to_deleteSet::add);

  • 使用深度优先搜索(DFS)遍历树

node.left = dfs(node.left, s, ans);
node.right = dfs(node.right, s, ans);

  • 当前节点处理逻辑

判断当前节点是否为待删除节点

  • 不是则返回节点,保持父子关系;
  • 当前节点为待删除节点:
    1. 添加左孩子、右孩子到结果集中【因为是DFS,所以不用考虑放入结果集中的孩子们是否也应该删除
    2. 删除当前节点【return null;】,断绝关系

代码编写

	/**
	 * 1110. 删点成林
	 * https://leetcode.cn/problems/delete-nodes-and-return-forest/description/
	 * @param root
	 * @param to_delete
	 * @return
	 */
	public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
	    if (Objects.isNull(root) || Objects.isNull(to_delete) || to_delete.length == 0) {
	        return Collections.singletonList(root);
	    }
	
	    // 确认是否需要删除node  O(1)
	    Set<Integer> to_deleteSet = new HashSet<>();
	    Arrays.stream(to_delete).forEach(to_deleteSet::add);
	
	    List<TreeNode> result = new ArrayList<>();
	    // DFS
	    if (!Objects.isNull(dfs(root, to_deleteSet, result))) {
	        result.add(root);
	    }
	
	    return result;
	}
	
	/**
	 * DFS->从下(子节点)向上(父节点)
	 * @param node
	 * @param s
	 * @param ans
	 * @return
	 */
	private TreeNode dfs(TreeNode node, Set<Integer> s, List<TreeNode> ans) {
	    if (Objects.isNull(node)) {
	        return null;
	    }
	    // 左
	    node.left = dfs(node.left, s, ans);
	    // 右
	    node.right = dfs(node.right, s, ans);
	
	    if (!s.contains(node.val)) {
	        // 当前节点不能删除(保持与父节点的链接)
	        return node;
	    }
	
	    // 当前节点为待删除的节点
	    if (!Objects.isNull(node.left)) {
	        ans.add(node.left);
	    }
	    if (!Objects.isNull(node.right)) {
	        ans.add(node.right);
	    }
	
	    // 删除当前节点(断开与父节点的链接)
	    return null;
	}

代码解析

  • 如果根节点为空或者删除数组为空,直接返回只含有根节点的列表。
  • 将待删除的节点值存入一个哈希集合 to_deleteSet 中。
  • 通过深度优先搜索(DFS)遍历树,判断当前节点是否需要删除。如果不需要删除,则递归遍历其左右子节点,并更新左右子节点的链接;如果需要删除,则将其左右子节点加入结果集 ans 中,并将当前节点删除。
  • 返回结果集 ans,即删除节点后的根节点集合。

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

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

相关文章

Orange3数据预处理(列选择组件)数据角色及类型描述

在Orange3的文件组件中&#xff0c;datetime、categorical、numeric以及text代表不同种类的数据类型&#xff0c;具体如下&#xff1a; datetime&#xff1a;代表日期和时间类型的数据。通常用于时间序列分析、生存分析和其他需要考虑时间因素的机器学习任务中。例如&#xff0…

英语连读技巧15

1. first one – 第一个 连读听起来就像是&#xff1a;【佛斯湾】 连读的音标为&#xff1a; 例句&#xff1a;I don’t want to be the first one there agin. 发音指导&#xff1a;在“first one”的连读中&#xff0c;"t"和"o"之间的连接几乎消失&a…

17.材质和外观

1.图形学中的材质 在图形学中&#xff0c;材质&#xff08;Material&#xff09;是用来描述物体外观和表面特性的属性集合。它包含了控制光的反射、折射、吸收以及其他光学效果的信息&#xff0c;从而决定了物体在渲染过程中的外观。 渲染方程中那一项和材质有关&#xff1f; …

RDMA内核态函数ib_post_recv()源码分析

接上文&#xff0c;上文分析了内核rdma向发送队列添加发送请求的函数ib_post_send&#xff0c;本文分析一下向接收队列添加接收请求的函数ib_post_recv。其实函数调用流程与上文类似&#xff0c;不再重复说明&#xff0c;可参考链接。 函数调用过程 最终会调用到这个函数 下面…

Git笔记——3

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 一、合并模式和分支策略 二、bug分支 三、强制删除分支 四、创建远程仓库 五、克隆远程仓库_HTTPS和_SSH 克隆远程仓库_HTTPS 克隆远程仓库_SSH 六、向远程仓库…

深入理解计算机系统——内部很重要的硬件

文章目录 计算机的内部硬件系统的硬件组成运行hello高速缓存Cache存储设备的层次结构 计算机的内部硬件 系统的硬件组成 1.总线 简单来说就是字节流在总线里面跑来跑去&#xff0c;通常这个被设计成一个传送定长的字节块&#xff0c;也就是字。 在计算机系统中&#xff0c;字…

react中使用echarts

先上一张效果图 React中 配置属性如下&#xff0c;可直接粘贴使用 import React, { useEffect, useMemo, useState } from react import * as echarts from echarts import ReactECharts from echarts-for-reactconst LineChart (props: any) > {const option {color: [#…

C++之std::tuple(二) : 揭秘底层实现原理

相关系列文章 C之std::tuple(二) : 揭秘底层实现原理 C三剑客之std::any(一) : 使用 C之std::tuple(一) : 使用精讲(全) C三剑客之std::variant(一) : 使用 C三剑客之std::variant(二)&#xff1a;深入剖析 深入理解可变参数(va_list、std::initializer_list和可变参数模版) st…

xss靶场实战(xss-labs-master靶场)

xss-labs-master靶场链接&#xff1a;https://pan.baidu.com/s/1X_uZLF3CWw2Cmt3UnZ1bTw?pwdgk9c 提取码&#xff1a;gk9c xss-labs level 1 修改 url 地址中的name<script>alert(1)</script>&#xff0c;便可以通关 level 2 在搜索框中输入的 JS 代码无法执行 …

Programming Abstractions in C阅读笔记:p293-p302

《Programming Abstractions in C》学习第73天&#xff0c;p293-p302总结&#xff0c;总计10页。 一、技术总结 1.时间复杂度 (1)quadratic time(二次时间) p293, Algorithms like selection sort that exhibit O(N^2) performance are said to run in quadratic time。 2…

windows实现ip1:port1转发至ip2:port2教程

第一步&#xff1a;创建虚拟网卡(如果ip1为本机127.0.0.1跳过此步骤)&#xff0c;虚拟网卡的IPV4属性设置ip1 1> 创建虚拟网卡参见 Windows系统如何添加虚拟网卡&#xff08;环回网络适配器&#xff09;_windows添加虚拟网卡-CSDN博客​​​​​​ 2> 设置虚拟网卡使用…

C++——类和对象(1)

1. 类 我们之前提及过C语言是面向过程的语言&#xff0c;其解决问题的方式是关注问题过程&#xff0c;然后逐步解决。而C是面向对象编程&#xff0c;聚焦于对象&#xff0c;依靠多个对象之间的交互关系解决问题。而类这个概念的引入则是面向对象的最深刻体现。 1.1 C中的结构体…

32单片机基础:OLED调试工具的使用

下面会介绍OLED显示屏的驱动函数模块&#xff0c;先学会如何使用&#xff0c;至于OLED屏幕的原理和代码编写&#xff0c; 我们之后会再写一篇。 现在我们就是用OLED当一个调试的显示屏&#xff0c;方便我们调试程序。 为什么要调试呢&#xff0c;是为了方便我们看现象&#…

人工智能 — 点云模型

目录 一、点云模型1、三维图像2、点云1、概念2、内容 3、点云处理的三个层次1、低层次处理方法2、中层次处理方法3、高层次处理方法 二、Spin image 一、点云模型 1、三维图像 三维图像是一种特殊的信息表达形式&#xff0c;其特征是表达的空间中三个维度的数据。 和二维图像…

涵盖5大领域的机器学习工具介绍

随着数据的产生及其使用量的不断增加&#xff0c;对机器学习模型的需求也在成倍增加。由于ML系统包含了算法和丰富的ML库&#xff0c;它有助于分析数据和做出决策。难怪机器学习的知名度越来越高&#xff0c;因为ML应用几乎主导了现代世界的每一个方面。随着企业对这项技术的探…

Mockito单元测试Mockito对Service层的测试案例

前言 以下是关于Mockito的API使用文档 官网&#xff1a;http://mockito.org/ 官网英文API文档&#xff1a;https://javadoc.io/static/org.mockito/mockito-core/5.10.0/help-doc.html#index 非官方中文API文档&#xff1a;https://gitee.com/wnboy/mockito-doc-zh#mockito-%E…

软件运维维保方案-套用文档

软件运维维保方案 项目情况 1.1 项目背景 简述项目的来源、目的和重要性。 说明项目的规模、预算和预期目标。 1.2 项目现状 分析当前系统/软件的运行状态、存在的问题和潜在风险。 提供最近一次的维护报告或相关统计数据。服务简述 2.1 服务内容 明确运维服务的具体内容&…

JSON(javaScript Object Notation,Js对象标记)—我耀学IT

Json是一种轻量级的数据交换格式&#xff0c;目前使用非常广泛&#xff0c;是一种轻量级的数据交换格式。易于人阅读和编写&#xff0c;可以在多种语言之间进行数据交换 。同时也易于机器解析和生成 1.1json的值: 值可以是对象、数组、数字、字符串或者三个字面值(false、nul…

【数据分析之Numpy基础003】数组形状大变身!轻松掌握改变数组形状的技巧

处理数组的一项重要工作就是改变数组的维度&#xff0c;包括提高数组的维度和降低数组的维度&#xff0c;还包括数组的转置、拼接、分隔等。 Numpy为大家提供了大量的API可以很轻松的完成这些数组的操作。 1、改变数组的维度 如上篇文章使用到的reshape方法&#xff0c;将一维…

各国的通胀是多少?央行又使用那些指标?昂首资本1分钟分享

各国的通胀是多少&#xff1f;央行又使用哪些指标&#xff1f;今天昂首资本1分钟快速分享 在美国和欧盟&#xff0c;作为一个中期通胀目标&#xff0c;使用了一个目标指标&#xff0c;通常是为长达两年的前景计算的。在美国和欧盟&#xff0c;中期通胀目标是2%。在俄罗斯&…