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

面试算法47:二叉树剪枝

题目

一棵二叉树的所有节点的值要么是0要么是1,请剪除该二叉树中所有节点的值全都是0的子树。例如,在剪除图8.2(a)中二叉树中所有节点值都为0的子树之后的结果如图8.2(b)所示。
在这里插入图片描述

分析

下面总结什么样的节点可以被删除。首先,这个节点的值应该是0。其次,如果它有子树,那么它的子树的所有节点的值都为0。也就是说,如果一个节点可以被删除,那么它的子树的所有节点都可以被删除。

由此发现,后序遍历最适合用来解决这个问题。如果用后序遍历的顺序遍历到某个节点,那么它的左右子树的节点一定已经遍历过了。每遍历到一个节点,就要确定它是否有左右子树,如果左右子树都是空的,并且节点的值是0,那么也就可以删除这个节点。

public class Test {public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node0 = new TreeNode(0);TreeNode node00 = new TreeNode(00);TreeNode node000 = new TreeNode(000);TreeNode node0000 = new TreeNode(0000);TreeNode node00000 = new TreeNode(00000);TreeNode node11 = new TreeNode(1);node1.left = node0;node1.right = node00;node0.left = node000;node0.right = node0000;node00.left = node00000;node00.right = node11;TreeNode result = pruneTree(node1);System.out.println(result);}public static TreeNode pruneTree(TreeNode root) {if (root == null) {return root;}root.left = pruneTree(root.left);root.right = pruneTree(root.right);if (root.left == null && root.right == null && root.val == 0) {return null;}return root;}
}

相关文章:

面试算法47:二叉树剪枝

题目 一棵二叉树的所有节点的值要么是0要么是1,请剪除该二叉树中所有节点的值全都是0的子树。例如,在剪除图8.2(a)中二叉树中所有节点值都为0的子树之后的结果如图8.2(b)所示。 分析 下面总结什么样的节…...

云安全-云原生k8s攻击点(8080,6443,10250未授权攻击点)

0x00 k8s简介 k8s(Kubernetes) 是容器管理平台,用来管理容器化的应用,提供快速的容器调度、弹性伸缩等诸多功能,可以理解为容器云,不涉及到业务层面的开发。只要你的应用可以实现容器化,就可以部…...

性能压力测试主要目标及步骤

性能压力测试是软件开发生命周期中至关重要的一部分,旨在评估应用程序或系统在高负载和极端条件下的性能表现。这种测试有助于发现性能瓶颈、资源耗尽和错误,以确保应用程序在真实使用情况下的可靠性和稳定性。本文将探讨性能压力测试的概念、方法和最佳…...

VLAN与配置

VLAN与配置 什么是VLAN 以最简单的形式为例。如下图,此时有4台主机处于同一局域网中,很明显这4台主机是能够直接通讯。但此时我需要让处于同一局域网中的PC3和PC4能通讯,PC5和PC6能通讯,并且PC3和PC4不能与PC5和PC6通讯。 为了实…...

API接口安全设计

简介 HTTP接口是互联网各系统之间对接的重要方式之一,使用HTTP接口开发和调用都很方便,也是被大量采用的方式,它可以让不同系统之间实现数据的交换和共享。 由于HTTP接口开放在互联网上,所以我们就需要有一定的安全措施来保证接口…...

服务器的管理口和业务口

服务器管理接口和业务接口 服务器管理接口(Server Management Interface,SMI): 服务器管理接口是一种用于管理服务器硬件和操作系统的标准接口。它通常用于远程管理和监控服务器,包括但不限于以下功能: …...

【gpt redis】原理篇

用的黑马程序员redis课程的目录,但是不想听讲了。后续都是用gpt文档获取的。 1.课程介绍(Av766995956,P145) 2.Redis数据结构-动态字符串(Av766995956,P146) sds 1M是个界限 其实他是个由c语言实现的结构体 有这么几个参数 len alloc flag char[] len是实际长度 …...

python二次开发Solidworks:排雷以及如何排雷?

目录 1、重要文档 2、MSDN VARIANTS 3、错误排除实例 3.1 第一个例子 3.2 第二个例子 1、重要文档 SolidWorks API 帮助文档:在 SolidWorks 的安装路径下可以找到本地文件,如 ...\Program Files\SolidWorks Corp\SolidWorks\api\apihelp.chm 。 s…...

广告引擎检索技术快速学习

目录 一、广告系统与广告引擎介绍 (一)广告系统与广告粗分 (二)广告引擎在广告系统中的重要性分析 二、广告引擎整体架构和工作过程 (一)一般概述 (二)核心功能架构图 三、标…...

Scala的类和对象

1. 初识类和对象 Scala 的类与 Java 的类具有非常多的相似性,示例如下: // 1. 在 scala 中,类不需要用 public 声明,所有的类都具有公共的可见性 class Person {// 2. 声明私有变量,用 var 修饰的变量默认拥有 getter/setter 属性private var…...

SQL中 <>(不等于)运算符只会匹配那些具有非空值的记录

0. 场景 idflag112null3 一张表的有有个varchar类型的flag字段,字段值有 null值/空值和 1。 flag为 1即表示逻辑删除,我想找出flag字段非 1 的所有情况: 一开始sql写法: select * from table where flag<>‘1’理想情况,结果集应该有2条记录(id为 2 和 3 的记录)实际情…...

冒泡排序(Java)

基本思想 比较前后相邻的二个数据&#xff0c;如果前面数据大于后面的数据&#xff0c;就将这二个数据交换。这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后&#xff0c;最大的一个数据就“沉”到数组第N-1 个位置。如此循环 (N-1)次&#xff0c;每次循环需要比较的个数…...

k8s集群调度

目录 1、理论&#xff1a; 1.1、 概述&#xff1a; 1.2、Pod 是 Kubernetes 的基础单元&#xff0c;Pod 启动典型创建过程如下&#xff1a; 工作机制 **** 1.3、调度过程 *** 1.4、Predicate 有一系列的常见的算法可以使用&#xff1a; ** 1.5、 优先级由一系列键…...

Scala中类的继承、抽象类和特质

1. 类的继承 1.1 Scala中的继承结构 Scala 中继承关系如下图&#xff1a; Any 是整个继承关系的根节点&#xff1b; AnyRef 包含 Scala Classes 和 Java Classes&#xff0c;等价于 Java 中的 java.lang.Object&#xff1b; AnyVal 是所有值类型的一个标记&#xff1b; Nul…...

小程序如何实现登录数据持久化

在小程序中实现登录数据的持久化可以通过以下几种方式&#xff1a; 使用本地缓存 在用户登录成功后&#xff0c;将登录凭证或用户信息等数据使用 wx.setStorageSync 方法存储到本地缓存中&#xff1a; // 存储登录数据到本地缓存 wx.setStorageSync(token, 登录凭证); wx.set…...

Maven本地配置获取nexus私服的依赖

场景 Nexus-在项目中使用Maven私服&#xff0c;Deploy到私服、上传第三方jar包、在项目中使用私服jar包&#xff1a; Nexus-在项目中使用Maven私服&#xff0c;Deploy到私服、上传第三方jar包、在项目中使用私服jar包_nexus maven-releases 允许deploy-CSDN博客 在上面讲的是…...

第02章-变量与运算符

1 关键字 关键字&#xff1a;被Java语言赋予了特殊含义&#xff0c;用作专门用途的字符串&#xff08;或单词&#xff09;。如class、public、static、void等&#xff0c;这些单词都被Java定义好了&#xff0c;称为关键字。 特点&#xff1a;关键字都是小写字母&#xff1b;官…...

SpringBoot数据响应、分层解耦、三层架构

响应数据 ResponseBody 类型&#xff1a;方法注解、类注解位置&#xff1a;Controller方法、类上作用&#xff1a;将方法返回值直接响应&#xff0c;如果返回值类型是 实体对象/集合 &#xff0c;将会转换为json格式响应说明&#xff1a;RestController Controller Respons…...

go测试库之apitest

&#x1f4e2;专注于分享软件测试干货内容&#xff0c;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; 如有错误敬请指正&#xff01;&#x1f4e2;交流讨论&#xff1a;欢迎加入我们一起学习&#xff01;&#x1f4e2;资源分享&#xff1a;耗时200小时精选的「软件测试」资…...

K8S删除资源后一直处于Terminating状态无法删除解决方法

原因 使用kubectl delete 删除某命名空间是一直处于Terminating状态无法删除&#xff0c;首先排查了该命名空间下是否还存在deployment pod等资源发现没有后&#xff0c;等了很久还是无法删除后发现是因为该名称空间的“finalizers”字段有值导致 Finalizer&#xff08;终结器…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...