[100天算法】-二叉树剪枝(day 48)

题目描述

给定二叉树根结点 root ,此外树的每个结点的值要么是 0,要么是 1。返回移除了所有不包含 1 的子树的原二叉树。( 节点 X 的子树为 X 本身,以及所有 X 的后代。)示例1:
输入: [1,null,0,0,1]
输出: [1,null,0,null,1]示例2:
输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]示例3:
输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]说明:给定的二叉树最多有 100 个节点。
每个节点的值只会为 0 或 1 。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-pruning
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

用【产品经理法】的思维来解决递归问题。

产品

假设我们已经有了一个 pruneTree 方法,可以把一棵树中不包含 1 的枝节删掉。

子问题

明显是 pruneTree(root.left) 和 pruneTree(root.right)

大小问题的关系

首先,对于 root,我们用 pruneTree(root.left) 和 pruneTree(root.right) 的结果分别替换掉原本的 root.left 和 root.right。接着,再决定当前这棵树要不要保留。

  • 如果此时左右子树有一个不为空的话,那说明这棵树是要保留的,直接返回 root 就行。
  • 如果左右子树都为空,那我们就判断 root.val 的值,等于 1 就返回 root,等于 0 就返回 null 把这棵树移除。

递归出口

空节点直接返回 null 就行。

代码

TypeScript Code

/*** Definition for a binary tree node.* class TreeNode {*     val: number*     left: TreeNode | null*     right: TreeNode | null*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {*         this.val = (val===undefined ? 0 : val)*         this.left = (left===undefined ? null : left)*         this.right = (right===undefined ? null : right)*     }* }*/function pruneTree(root: TreeNode | null): TreeNode | null {if (!root) return null;root.left = pruneTree(root.left);root.right = pruneTree(root.right);return root.left || root.right || root.val === 1 ? root : null;
}

复杂度分析

  • 时间复杂度:$O(N)$,N 为二叉树节点数。
  • 空间复杂度:$O(H)$,H 为二叉树的高度,递归栈的最大空间。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/176912.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【C++的OpenCV】第十四课-OpenCV基础强化(三):单通道Mat元素的访问之data和step属性

🎉🎉🎉 欢迎来到小白 p i a o 的学习空间! \color{red}{欢迎来到小白piao的学习空间!} 欢迎来到小白piao的学习空间!🎉🎉🎉 💖 C\Python所有的入门技术皆在 我…

STM32F407的系统定时器

文章目录 系统定时器SysTick滴答定时器寄存器STK_CTRL 控制寄存器STK_LOAD 重载寄存器STK_VAL 当前值寄存器STK_CALRB 校准值寄存器 初始化 Systick 定时器SysTick_InitSysTick_CLKSourceConfig delay_us寄存器delay_us库函数delay_xms短时delay_ms长时SysTick_Config 系统定时…

HTML和CSS的基础-前端扫盲

想要写出一个网页,就需要学习前端开发(写网页代码)和后端开发(服务器代码)。 对于前端的要求,我们不需要了解很深,仅仅需要做到扫盲的程度就可以了。 写前端,主要用到的有&#xf…

〔001〕虚幻 UE5 发送 get、post 请求、读取 json 文件

✨ 目录 🎈 安装 varest 扩展🎈 开启 varest 扩展🎈 发送 get 请求🎈 发送 post 请求🎈 读取 json 文件🎈 安装 varest 扩展 打开 虚幻商城,搜索 varest 关键字进行检索, varest 是一个 api 调用插件,支持 http/https 请求,也支持 json 文件的读取,最关键是该…

JavaScript

一. JavaScript概述 1. ECMAScript和JavaScript的关系 1996年11月,JavaScript的创造者--Netscape公司,决定将JavaScript提交给国际标准化组织ECMA,希望这门语言能够成为国际标准。次年,ECMA发布262号标准文件(ECMA-26…

水库大坝可视化智能远程监管方案,助力安全监测智能巡检

一、背景需求 水库大坝作为防洪度汛的重要设施,其安全问题直接关系到人民群众的生命财产安全。因此,必须加强对大坝水库的安全管理,对水库除险加固和运行管护要消除存量隐患,实现常态化管理,同时要配套完善重点小型水…

在Linux上编译gdal3.1.2指南

作者:朱金灿 来源:clever101的专栏 为什么大多数人学不会人工智能编程?>>> 以Ubuntu 18编译gdal3.1.2为例,编译gdal3.1.2需要先编译proj库和geos库(可选)。我选择的proj库版本为proj-7.1.0,编译proj-7.1.0需要先编译tiff库和sqlite3。我选择的sqlite3的版本为…

高性能消息中间件 - Kafka3.x(三)

文章目录 高性能消息中间件 - Kafka3.x(三)Kafka Broker ⭐Kafka Broker概念Zookeeper(新版本可以不使用zk了)⭐Zookeeper的作用 Kafka的选举1:Broker选举Leader⭐Broker核心参数⭐案例:服役新节点和退役旧…

SaaS可配置性设计要点

1 引言 考虑到系统SaaS需求,就成熟的SaaS应用而言,元数据服务是为用户提供定制和配置应用、满足其特定需求的主要手段。 可配置能力主要反映在这4个方面:1 程序外观;2 工作流程与业务规则;3 数据模型&#xff1b…

微信便利签怎么弄?微信中有便捷操作的便签小程序吗

微信在日常办公及生活中比较重要的作用就是:聊天、视频会议、语音会议等,这是大家认知中的微信。除了这些功能以外,微信中还有很多小程序,小程序也能够辅助大家日常的办公。 比如,工作中我们需要制定工作计划&#xf…

vscode开启emmet语法

需要在setting.json中添加配置 首先进入设置,然后点击右上角 Vue项目添加如下配置 "emmet.syntaxProfiles": { "vue-html": "html", "vue": "html" },React项目添加如下配置 "emmet.includeLanguages&quo…

一体化模型图像去雨+图像去噪+图像去模糊(图像处理-图像复原-代码+部署运行教程)

本文主要讲述了一体化模型进行去噪、去雨、去模糊,也就是说,一个模型就可以完成上述三个任务。实现了良好的图像复原功能! 先来看一下美女复原.jpg 具体的: 在图像恢复任务中,需要在恢复图像的过程中保持空间细节…

transformers-Generation with LLMs

https://huggingface.co/docs/transformers/main/en/llm_tutorialhttps://huggingface.co/docs/transformers/main/en/llm_tutorial停止条件是由模型决定的,模型应该能够学习何时输出一个序列结束(EOS)标记。如果不是这种情况,则在…

Mybatis—基础操作

mybatis入门后,继续学习mybatis基础操作。 目录 Mybatis基础操作准备工作删除操作日志输入预编译SQLSQL注入参数占位符 新增操作基本新增添加后返回主键 更新操作查询操作根据id查询数据封装条件查询条件查询 Mybatis基础操作 准备工作 根据下面页面原型及需求&am…

vlc打开网络流(如rtmp),并查看媒体信息(如编码格式等编码信息)

打开vlc 选择媒体,打开网络串流 输入rtmp地址,点击播放 选择工具-编解码信息 可以查看节目的编码信息什么的

SpringCloud 微服务全栈体系(九)

第九章 Docker 三、Dockerfile 自定义镜像 常见的镜像在 DockerHub 就能找到,但是我们自己写的项目就必须自己构建镜像了。 而要自定义镜像,就必须先了解镜像的结构才行。 1. 镜像结构 镜像是将应用程序及其需要的系统函数库、环境、配置、依赖打包而…

Reading:Deep dive into the OnPush change detection strategy in Angular

原文连接:IndepthApp 今天深入阅读并总结Angualr中onPush更新策略。 1. 两种策略 & whats Lview? Angular 实现了两种策略来控制各个组件级别的更改检测行为。这些策略定义为Default和OnPush: 被定义为枚举: export enum…

Spring系统之IOC与AOP

前言 Spring是一个轻量级的控制反转(IoC)和面向切面(AOP)的容器框架。 IOC 1.IOC的概念 控制反转(IoCInversion of Control)IoC,用白话来讲,就是由容器控制程序之间的(依赖)关系,而非传统实现中,由程序代码…

python manage.py createsuperuser运行错误

我把思念作笺,随风而去,落在你常路过的那个街角… 错误复现 PS D:\教学文件\Django\djangoProject\webDemo02> python manage.py createsuperuser System check identified some issues:WARNINGS: ?: (urls.W005) URL namespace admin isnt unique…

Maven入门与开箱即用

一、初识 Maven(了解) 1、项目遇到的问题 构建:编译代码,运行测试,打包,部署应用,运行服务器等;依赖:项目依赖大量的第三方包,第三方包又依赖另外的包&…