二叉树题目:二叉树剪枝
文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题:二叉树剪枝
出处:814. 二叉树剪枝
难度
4 级
题目描述
要求
给定二叉树的根结点 root \texttt{root} root,返回移除了所有不包含 1 \texttt{1} 1 的子树的原二叉树。
结点 node \texttt{node} node 的子树为 node \texttt{node} node 本身以及所有 node \texttt{node} node 的后代。
示例
示例 1:

输入: root = [1,null,0,0,1] \texttt{root = [1,null,0,0,1]} root = [1,null,0,0,1]
输出: [1,null,0,null,1] \texttt{[1,null,0,null,1]} [1,null,0,null,1]
解释:
只有红色结点满足条件「所有不包含 1 \texttt{1} 1 的子树」。右图为返回的答案。
示例 2:

输入: root = [1,0,1,0,0,0,1] \texttt{root = [1,0,1,0,0,0,1]} root = [1,0,1,0,0,0,1]
输出: [1,null,1,null,1] \texttt{[1,null,1,null,1]} [1,null,1,null,1]
示例 3:

输入: root = [1,1,0,1,1,0,1,0] \texttt{root = [1,1,0,1,1,0,1,0]} root = [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1] \texttt{[1,1,0,1,1,null,1]} [1,1,0,1,1,null,1]
数据范围
- 树中结点数目在范围 [1, 200] \texttt{[1, 200]} [1, 200] 内
- Node.val \texttt{Node.val} Node.val 是 0 \texttt{0} 0 或 1 \texttt{1} 1
解法
思路和算法
如果二叉树为空,则不需要执行剪枝操作,直接返回即可。
当二叉树不为空时,需要首先对二叉树的左子树和右子树执行剪枝操作,然后对当前二叉树执行剪枝操作。剪枝操作具体为,如果一个结点是叶结点且结点值为 0 0 0,则该结点被移除。注意在移除值为 0 0 0 的叶结点之后,被移除的结点的父结点可能从非叶结点变成叶结点。
由于每个结点是否需要被移除和结点的子树有关,因此可以使用深度优先搜索实现。
整个过程是一个递归的过程。递归的终止条件是当前结点为空,或者当前结点是叶结点且结点值为 0 0 0,这两种情况都返回空二叉树。对于其余情况,递归地对左子树和右子树执行剪枝操作。
由于剪枝操作只会移除所有的值为 0 0 0 的叶结点(包括从非叶节点变成叶结点的值为 0 0 0 的结点),不会移除值为 1 1 1 的结点,因此剪枝操作可以确保移除所有不包含 1 1 1 的子树。
代码
class Solution {public 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) {root = null;}return root;}
}
复杂度分析
-
时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点都被访问一次。
-
空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间,取决于二叉树的高度,最坏情况下二叉树的高度是 O ( n ) O(n) O(n)。
相关文章:
二叉树题目:二叉树剪枝
文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题:二叉树剪枝 出处:814. 二叉树剪枝 难度 4 级 题目描述 要求 给定二叉树的根结点 root \texttt{root} root,返回移除了所有…...
JAVA中使用CompletableFuture进行异步编程
JAVA中使用CompletableFuture进行异步编程 1、什么是CompletableFuture CompletableFuture 是 JDK8 提供的 Future 增强类,CompletableFuture 异步任务执行线程池,默认是把异步任 务都放在 ForkJoinPool 中执行。 在这种方式中,主线程不会…...
uniapp:配置动态接口域名,根据图片访问速度,选择最快的接口
common.js // 动态测速选择的域名 // h5直接返回默认第一个域名 // vue文件用到域名的话用this.$baseURL let domains [{uri:192.168.31.215:9523, speed:0},{uri:api.ceshi.org, speed:0}, ]export const protocol {api: http://,//本地// api: https://api.,//正式h5Url: h…...
Lambda表达式常见用法(提高效率神器)
Java8中一个非常重要的特性就是Lambda表达式,我们可以把它看成是一种闭包,它允许把函数当做参数来使用,是面向函数式编程的思想,一定程度上可以使代码看起来更加简洁。 其实以上都不重要,重要的是能够提高我的开发效率…...
2023旷视自驾感知算法暑期实习一面
来源:投稿 作者:LSC 编辑:学姐 1. 问下项目,问下我的情况 2. 是否了解最新的BEV算法,讲一下 3. 是否了解三维重建 4. 考察相机坐标系的转换 5. 手撕代码,翻车了,不考leetcode,考…...
Python3 如何实现 websocket 服务?
Python 实现 websocket 服务很简单,有很多的三方包可以用,我从网上大概找到三种常用的包:websocket、websockets、Flask-Sockets。 但这些包很多都“年久失修”, 比如 websocket 在 2010 年就不维护了。 而 Flask-Sockets 也在 2…...
SQLAlchemy常用数据类型
目录 SQLAlchemy常用数据类型 代码演示 代码分析 SQLAlchemy常用数据类型 SQLAlchemy 是一个Python的SQL工具库和对象关系映射(ORM)工具,它提供了一种在Python中操作数据库的高效方式。下面是SQLAlchemy中常用的一些数据类型: Integer:整形&…...
Vue路由与nodejs下载安装及环境变量的配置
目录 前言 一、Vue路由 1.路由简介 是什么 作用 应用场景 2.SPA简介 SPA是什么 SPA的优点 注意事项 3.路由实现思路 1.引入路由的js依赖 2.定义组件 3.定义组件与路径的对应关系 4.通过路由关系获取路由对象router 5.将路由对象挂载到实例中 6.触发路由事…...
HarmonyOS之 应用程序页面UIAbility
一 UIAbility介绍: 1.1 UIAbility是一种包含用户界面的应用组件,主要用于和用户进行交互 1.2 UIAbility也是系统调度的单元,为应用提供窗口在其中绘制界面 二 UIAbility跳转和传参 2.1 页面间的导航可以通过页面路由router模块来实现。页…...
数据集笔记: Porto
数据来源:Taxi Trajectory Data_数据集-阿里云天池 (aliyun.com) 1 数据介绍 葡萄牙波尔图市运行的所有442辆出租车的全年轨迹(从2013年7月1日至2014年6月30日) 2 读取数据 import pandas as pdtrapd.read_csv(C:/Users/16000/Download…...
修改vscode底部栏背景和字体颜色
修改vscode底部栏背景和字体颜色 如图: 首先打开齿轮,打开设置搜索workbench.colorCustomizations,然后点击编辑setting.json修改setting.json内内容 "workbench.colorCustomizations": {"statusBar.foreground": "#FFFFFF…...
加速企业AI实施:成功策略和效率方法
文章目录 写在前面面临的挑战MlOps简介好书推荐 写作末尾 写在前面 作为计算机科学领域的一个关键分支,机器学习在当今人工智能领域中占据着至关重要的地位,广受瞩目。机器学习通过深入分析大规模数据并总结其中的规律,为我们提供了解决许多…...
【图论C++】树的重心——教父POJ 3107(链式前向星的使用)
》》》算法竞赛 /*** file * author jUicE_g2R(qq:3406291309)————彬(bin-必应)* 一个某双流一大学通信与信息专业大二在读 * * brief 一直在竞赛算法学习的路上* * copyright 2023.9* COPYRIGHT 原创技术笔记:转载…...
hhh百度地铁广告太搞笑了;24家国内大模型公司面经;LLM法律应用实践;AI+教育产品图谱与工作流 | ShowMeAI日报
👀日报&周刊合集 | 🎡生产力工具与行业应用大全 | 🧡 点赞关注评论拜托啦! 🔥 会玩儿!承包地铁专列,真人移动广告 | 百度世界大会预热 百度也是会玩儿!承包了北京地铁一号线的「…...
项目管理:项目经理一定要避开这四大误区
项目经理要保质保量按时达成项目目标,需要关注项目的方方面面,要具有很强的沟通协调能力和目标意识。但是项目经理也不免不了失误,管理中的这四大误区,你经历过几个? 误区一:做不该做的事 你是否遇到这种…...
爬虫为什么需要 HTTP 代理 IP?
前言 爬虫在互联网数据采集、分析和挖掘中扮演着至关重要的角色,但是对于目标网站而言,频繁的爬虫请求可能会对其服务器产生不小的负担,严重的情况甚至会导致网站崩溃或者访问受限。为了避免这种情况的发生,同时也为了保护客户端…...
leetcode刷题笔记/代码随想录笔记——移除字符串中多余空格
1. 使用erase()函数 void removeExtraSpaces(string& s) {for (int i s.size() - 1; i > 0; i--) {if (s[i] s[i - 1] && s[i] ) {s.erase(s.begin() i);}}// 删除字符串最后面的空格if (s.size() > 0 && s[s.size() - 1] ) {s.erase(s.begi…...
dataGrip导出导入的方式
导出:选中需要导出的表 导入:选中导出的sql文件...
LeetCode279. 完全平方数
279. 完全平方数 文章目录 [279. 完全平方数](https://leetcode.cn/problems/perfect-squares/)一、题目二、题解方法一:完全背包二维数组方法二:一维数组(空间复杂度更小的改进版本,最下面的两个版本不需要存储完全平方数) 一、题…...
【CMake】add_dependencies 命令
【CMake】add_dependencies 原文链接:https://blog.csdn.net/new9232/article/details/125831009 参考链接:https://blog.csdn.net/new9232/article/details/121374943 简介 add_dependencies(<target> [<target-dependency>]...)官方文档…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
