面试算法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(终结器…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
Linux安全加固:从攻防视角构建系统免疫
Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...
react更新页面数据,操作页面,双向数据绑定
// 路由不是组件的直接跳转use client,useEffect,useRouter,需3个结合, use client表示客户端 use client; import { Button,Card, Space,Tag,Table,message,Input } from antd; import { useEffect,useState } from react; impor…...
