当前位置: 首页 > 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;终结器…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...