面试算法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)
基本思想 比较前后相邻的二个数据,如果前面数据大于后面的数据,就将这二个数据交换。这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1 个位置。如此循环 (N-1)次,每次循环需要比较的个数…...
k8s集群调度
目录 1、理论: 1.1、 概述: 1.2、Pod 是 Kubernetes 的基础单元,Pod 启动典型创建过程如下: 工作机制 **** 1.3、调度过程 *** 1.4、Predicate 有一系列的常见的算法可以使用: ** 1.5、 优先级由一系列键…...
Scala中类的继承、抽象类和特质
1. 类的继承 1.1 Scala中的继承结构 Scala 中继承关系如下图: Any 是整个继承关系的根节点; AnyRef 包含 Scala Classes 和 Java Classes,等价于 Java 中的 java.lang.Object; AnyVal 是所有值类型的一个标记; Nul…...
小程序如何实现登录数据持久化
在小程序中实现登录数据的持久化可以通过以下几种方式: 使用本地缓存 在用户登录成功后,将登录凭证或用户信息等数据使用 wx.setStorageSync 方法存储到本地缓存中: // 存储登录数据到本地缓存 wx.setStorageSync(token, 登录凭证); wx.set…...
Maven本地配置获取nexus私服的依赖
场景 Nexus-在项目中使用Maven私服,Deploy到私服、上传第三方jar包、在项目中使用私服jar包: Nexus-在项目中使用Maven私服,Deploy到私服、上传第三方jar包、在项目中使用私服jar包_nexus maven-releases 允许deploy-CSDN博客 在上面讲的是…...
第02章-变量与运算符
1 关键字 关键字:被Java语言赋予了特殊含义,用作专门用途的字符串(或单词)。如class、public、static、void等,这些单词都被Java定义好了,称为关键字。 特点:关键字都是小写字母;官…...
SpringBoot数据响应、分层解耦、三层架构
响应数据 ResponseBody 类型:方法注解、类注解位置:Controller方法、类上作用:将方法返回值直接响应,如果返回值类型是 实体对象/集合 ,将会转换为json格式响应说明:RestController Controller Respons…...
go测试库之apitest
📢专注于分享软件测试干货内容,欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正!📢交流讨论:欢迎加入我们一起学习!📢资源分享:耗时200小时精选的「软件测试」资…...
K8S删除资源后一直处于Terminating状态无法删除解决方法
原因 使用kubectl delete 删除某命名空间是一直处于Terminating状态无法删除,首先排查了该命名空间下是否还存在deployment pod等资源发现没有后,等了很久还是无法删除后发现是因为该名称空间的“finalizers”字段有值导致 Finalizer(终结器…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
