二叉树题目:删点成林

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:删点成林

出处:1110. 删点成林

难度

6 级

题目描述

要求

给定二叉树的根结点 root \texttt{root} root,树中每个结点的值各不相同。

在删除所有结点值在 to_delete \texttt{to\_delete} to_delete 中出现的结点之后,得到一个森林(一些不相交的树构成的集合)。

返回森林中的每个树的根结点。可以按任意顺序返回答案。

示例

示例 1:

示例 1

输入: root = [1,2,3,4,5,6,7], to_delete = [3,5] \texttt{root = [1,2,3,4,5,6,7], to\_delete = [3,5]} root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出: [[1,2,null,4],[6],[7]] \texttt{[[1,2,null,4],[6],[7]]} [[1,2,null,4],[6],[7]]

示例 2:

输入: root = [1,2,4,null,3], to_delete = [3] \texttt{root = [1,2,4,null,3], to\_delete = [3]} root = [1,2,4,null,3], to_delete = [3]
输出: [[1,2,4]] \texttt{[[1,2,4]]} [[1,2,4]]

数据范围

  • 树中结点数目最大为 1000 \texttt{1000} 1000
  • 每个结点都有一个介于 1 \texttt{1} 1 1000 \texttt{1000} 1000 之间的各不相同的值
  • to_delete.length ≤ 1000 \texttt{to\_delete.length} \le \texttt{1000} to_delete.length1000
  • to_delete \texttt{to\_delete} to_delete 包含介于 1 \texttt{1} 1 1000 \texttt{1000} 1000 之间的各不相同的值

解法

思路和算法

对于二叉树中的每个结点,如果结点值在给定的数组中,则该结点需要删除。为了快速判断结点值是否在给定的数组中,应使用哈希集合存储给定的数组中的每个值。

删除结点之后得到的森林中的每个树的根结点可能有如下两种情况。

  • 如果根结点没有被删除,则根结点是森林中的一个树的根结点;如果根结点被删除,则根结点不在森林中。

  • 对于被删除的结点,其每个非空结点都是森林中的一个树的根结点。

可以使用深度优先搜索实现。从根结点开始搜索,搜索过程中需要记录当前结点的父结点是否被删除,如果父结点被删除则当前结点在不被删除的情况下需要加入森林,如果父结点不被删除则当前结点不加入森林。

由于根结点没有父结点,因此根结点的父结点记为被删除。对于每个结点,深度优先搜索执行如下操作。

  1. 如果当前结点的父结点被删除且当前结点不被删除,则将当前结点加入森林。

  2. 对于当前结点的每个非空子结点继续深度优先搜索,并更新当前结点的子结点的状态,其中子结点的父结点是否被删除的信息即为当前结点是否被删除的信息。

  3. 如果当前结点被删除则返回空结点,如果当前结点不被删除则返回当前结点。

上述操作中,如果一个结点的父结点被删除,则该结点作为一个新树的根结点加入森林中。对于每个结点,其在深度优先搜索中的返回值取决于该结点是否被删除。因此上述操作可以得到正确的结果。

代码

class Solution {Set<Integer> toDeleteSet = new HashSet<Integer>();List<TreeNode> forest = new ArrayList<TreeNode>();public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {for (int val : to_delete) {toDeleteSet.add(val);}dfs(root, true);return forest;}public TreeNode dfs(TreeNode node, boolean parentDelete) {boolean currDelete = toDeleteSet.contains(node.val);if (parentDelete && !currDelete) {forest.add(node);}TreeNode left = node.left, right = node.right;if (left != null) {node.left = dfs(left, currDelete);}if (right != null) {node.right = dfs(right, currDelete);}return currDelete ? null : node;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点都被访问一次。

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间,取决于二叉树的高度,最坏情况下是 O ( n ) O(n) O(n)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

阿里云ECS服务器无法访问端口(防火墙在关闭状态也启作用)

问题&#xff1a;一直用得好好的端口&#xff0c;突然在某一时间不可以访问这个端口了 &#xff0c;在服务器录入外网地址访问如下图&#xff1a; 先按正常流程检测&#xff1a; 1 先云服务商的管理网站查看防火墙端口是否开放 看了正常开放了端口&#xff0c;如下图&#xff…

Apollo自动驾驶系统:实现城市可持续交通的迈向

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 ChatGPT体验地址 文章目录 前言引言&#xff1a;1. 什么是微服务架构&#xff1f;2. 微服务架构的组成要素3. 微服务架构的挑战和解决方案4. 微服务架构的可扩展性和弹性 第二部分&#x…

亚马逊站内广告位置在哪设置?怎么设置广告位置?-站斧浏览器

亚马逊站内广告位置在哪设置&#xff1f; 亚马逊提供了多种广告类型&#xff0c;包括&#xff1a; Sponsored Products&#xff08;赞助产品&#xff09;&#xff1a;在搜索结果和商品详情页中展示。 Sponsored Brands&#xff08;赞助品牌&#xff09;&#xff1a;在搜索结…

kotlin基础——重载

重载算术运算符 重载二元算术运算 使用operator定义plus()方法后&#xff0c;可以直接使用号求和 data class Point(val x: Int, val y: Int) {operator fun plus(other: Point): Point {return Point(x other.x, y other.y)} } val p1 Point(1, 2) val p2 Point(3, 4) …

修改选择框el-select样式,显示及下拉样式

修改选择框el-select样式,显示及下拉样式 .el-input__inner {background: rgba(25, 126, 195, 0.2);border: none;color: #fff; }.el-select-dropdown {background: rgba(19, 73, 104, 0.79);border: 2px solid #48e3ff;border-radius: 0; }.el-popper .popper__arrow {display…

java设计模式学习之【策略模式】

文章目录 引言策略模式简介定义与用途实现方式 使用场景优势与劣势在Spring框架中的应用计算示例代码地址 引言 设想你正在玩一个策略游戏&#xff0c;每一个决策都会导致不同的游戏结局。同样地&#xff0c;在软件开发中&#xff0c;我们常常需要根据不同的场景或条件选择不同…

EOS链Ubuntu环境Install Prebuilt Binaries(安装预构建的二进制文件)的安装

[TOC](EOS链Ubuntu环境Install Prebuilt Binaries(安装预构建的二进制文件)的安装) EOS官网&#xff1a;https://eos.io/ 第一步 Ubuntu安装命令&#xff1a; 以下有两种安装方式&#xff0c;可以任选其一&#xff1a; 本文章已经上传绑定资源&#xff0c;也可以用命令安装。…

QT上位机开发(简易图像处理软件)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 大家都知道图像处理非常地重要&#xff0c;因为它不仅仅是可以用于拍照美颜&#xff0c;而且在工业、医疗和军事等方面也发挥着巨大的作用。另外一…

react-router-dom5升级到6

前言 升级前版本为5.1.2 下载与运行 下载 npm install react-router-dom6运行 运行发现报错: 将node_modules删除&#xff0c;重新执行npm i即可 运行发现如下报错 这是因为之前有引用react-router-dom.min&#xff0c;v6中取消了该文件&#xff0c;所以未找到文件导致报错。…

MO 2023 年度回顾

PART-ONE 行业态势 随着供需关系的变化&#xff0c;数据库的竞争在经历了 3 年 “百花齐放” 般的发展后&#xff0c;终于在 2023 年进入到了一个相对收拢的阶段。 2023 年&#xff0c;各个数据库厂商间很有默契地在两个方面达成了一致&#xff1a; HTAP 已经成为新一代数据…

前端下载文件问题之如何获取报错信息

问题&#xff1a;点击下载后。接口会生成并返回文件流。在极端情况下接口数据返回异常&#xff0c;需要抛出错误信息&#xff0c;比如后端拼接错误等情况、空文件情况。 难点&#xff1a;responseType设置为Blob后&#xff0c;返回内容为二进制文件流&#xff0c;从而无法获取错…

Linux_源码编译安装LAMP

1. 安装httpd服务 在配置 Apache 网站服务之前&#xff0c;需要正确安装好 httpd 服务器软件。httpd 服务器的安装可以选用 RPM 安装、源码编译安装这两种方式&#xff0c;前者相对比较简单、快速&#xff0c;但是在功能上存在一定的局限性。在实际的生产环境中&#xff0c;使…

堆排序算法

堆排序是利用堆这种数据结构而设计的一种排序算法&#xff0c;堆具有以下特点&#xff1a; 1.完全二叉树 2.二叉树每个结点的值都大于或等于其左右结点的值&#xff0c;称为大顶堆&#xff1b;或者每个结点的值都小于或等于其左右子结点的值&#xff0c;称为小顶堆 大顶堆 大…

马蹄集oj赛(双周赛第十八次)

目录 幸运的3 打靶 照亮街道 九次九日九重色 寻找串 竹鼠的白色季节 捉迷藏 好的三连 三角数 买马 可怜的小码哥 花园浇水 高次方程 幸运的3 难度:黄金时间限制: 1秒四占用内存:128M 你有 n 个数&#xff0c;可以将它们两两匹配(即将两数首尾相连)&#xff0c;每个…

基于Java+SpringBoot+vue+elementUI私人健身教练预约管理系统设计实现

基于JavaSpringBootvueelementUI私人健身教练预约管理系统设计实现 欢迎点赞 收藏 ⭐留言 文末获取源码联系方式 文章目录 基于JavaSpringBootvueelementUI私人健身教练预约管理系统设计实现一、前言介绍&#xff1a;二、系统设计&#xff1a;2.1 性能需求分析2.2 B/S架构&…

Stable Diffusion汉化插件

今天为大家介绍Stable Diffusion的两种UI汉化包&#xff0c;一种是汉化包&#xff0c;就中文界面&#xff0c;方便大家对于繁杂的参数的模型的操作&#xff0c;一种是中英文对照界面&#xff0c;在中文提示下&#xff0c;同时显示英文&#xff0c;不但方便设置也同时学习了英文…

Vue3 自定义Hooks大全:一站式解决你的疑惑!

前言 不知道喜欢 vue3 的小伙伴和我是不是一样&#xff0c;刚上手vue3 的时候 对自定义hooks 一脸懵逼&#xff0c;在一些视频网站学习的时候老师讲解到自定义hooks 最喜欢用 加减乘除来描述 自定义hooks 是咋用的&#xff0c;可能是我理解能力比较差吧&#xff0c;我看了这个…

程序媛的mac修炼手册-- 终端shell的驾驭 zsh vs bash

进入终端(Terminal)为新下载的应用配置环境&#xff0c;是Mac生产力up up的关键一步&#xff0c;更是编程小白装大神的第一步。Fake it till you make it , 硅谷大神标准路径&#xff5e; shell的基本原理 为应用配置环境&#xff0c;相当于在应用和操作系统间架桥。由此&…

VSCode使用Remote SSH远程连接Windows 7

结论 VSCode Server不能启动&#xff0c;无法建立连接。 原因 .vscode-server 目录中的 node.exe 无法运行。 原因是Node.js仅在Windows 8.1、Windows Server 2012 R2或更高版本上受支持。 由于vscode基于node.js v14&#xff0c;不支持Windows 7操作系统。 另&#xff…

低成本高效率易部署,Ruff工业数采网关+IoT云平台赋能工厂数字化管理

随着工业4.0的快速发展&#xff0c;工业物联网是工业企业实现数字化转型的重要助力&#xff0c;物联网技术的应用也越来越广泛。 作为连接设备与网络的关键节点&#xff0c;数据采集网关是连接工业设备与物联网平台的硬件设备&#xff0c;它负责将工业设备的数据采集、传输到物…