当前位置: 首页 > news >正文

二叉树题目:二叉树剪枝

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:二叉树剪枝

出处:814. 二叉树剪枝

难度

4 级

题目描述

要求

给定二叉树的根结点 root \texttt{root} root,返回移除了所有不包含 1 \texttt{1} 1 的子树的原二叉树。

结点 node \texttt{node} node 的子树为 node \texttt{node} node 本身以及所有 node \texttt{node} node 的后代。

示例

示例 1:

示例 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:

示例 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:

示例 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 原文链接&#xff1a;https://blog.csdn.net/new9232/article/details/125831009 参考链接&#xff1a;https://blog.csdn.net/new9232/article/details/121374943 简介 add_dependencies(<target> [<target-dependency>]...)官方文档…...

Python 爬虫进阶技巧:JSON 数据多层嵌套解析取值技巧

前言 在现代网络数据采集场景中,JSON(JavaScript Object Notation)已成为前后端数据交互的核心格式,绝大多数动态网页、API 接口均采用多层嵌套 JSON 结构传输数据。对于爬虫开发者而言,基础的 JSON 取值仅能应对简单数据结构,而面对深度嵌套、数组嵌套、混合嵌套等复杂…...

【限时决策窗口】ChatGPT Plus会员购买指南:避开3个高发误区,抓住GPT-4 Turbo+文件解析+自定义GPT三重红利期

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;ChatGPT Plus会员值不值得买 ChatGPT Plus 提供每月 $20 的订阅服务&#xff0c;主打 GPT-4 模型访问、高优先级响应队列、文件上传解析&#xff08;PDF/CSV/TXT 等&#xff09;及自定义 GPTs 功能。是…...

CFD热分析中绝热传热系数与叠加核函数原理及应用

1. CFD热分析中的绝热传热系数与叠加核函数原理剖析在电子设备热管理领域&#xff0c;随着功率密度的不断提升&#xff0c;传统的热设计方法已难以满足精度和效率的双重要求。绝热传热系数(Adiabatic Heat Transfer Coefficient, AHTC)与叠加核函数(Superposition Kernel Funct…...

2026届毕业生推荐的降重复率助手横评

Ai论文网站排名&#xff08;开题报告、文献综述、降aigc率、降重综合对比&#xff09; TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 使AI生成内容检测率降低的关键策略是让文本的自然性以及多样性得到增强。其一&#xff0c;别…...

如何在英雄联盟中节省70%的准备时间?这个本地工具告诉你答案

如何在英雄联盟中节省70%的准备时间&#xff1f;这个本地工具告诉你答案 【免费下载链接】League-Toolkit An all-in-one toolkit for LeagueClient. Gathering power &#x1f680;. 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 想象一下这个场景&…...

Cursor AI Pro破解工具2025:终极免费方案解决试用限制问题

Cursor AI Pro破解工具2025&#xff1a;终极免费方案解决试用限制问题 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached your…...

2025届学术党必备的五大AI学术助手实测分析

Ai论文网站排名&#xff08;开题报告、文献综述、降aigc率、降重综合对比&#xff09; TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek AI论文工具在当代学术领域&#xff0c;已然成为了极为关键的辅助支撑力量&#xff0c;它可全…...

基于MCP协议与AI的智能收据处理服务器:从OCR到结构化提取实战

1. 项目概述&#xff1a;一个专为收据处理而生的MCP服务器如果你经常需要处理各种格式的收据、发票或账单&#xff0c;无论是个人记账、公司报销&#xff0c;还是财务审计&#xff0c;那么你肯定对“数据录入”这个繁琐环节深恶痛绝。一张张纸质或电子收据&#xff0c;上面的关…...

Langchain和langgraph做什么的

...

告别时钟线!用三根线搞定高速传输:MIPI C-PHY硬件连接与编码原理详解

告别时钟线&#xff01;用三根线搞定高速传输&#xff1a;MIPI C-PHY硬件连接与编码原理详解 在高速数据传输领域&#xff0c;传统并行总线的时钟同步机制已成为提升速率的瓶颈。MIPI联盟推出的C-PHY标准&#xff0c;以革命性的"三线无时钟"架构打破了这一僵局。本文…...