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

C++二叉树剪枝

文章目录

  • C++二叉树剪枝
  • 题目链接
  • 题目描述
  • 解题思路
  • 代码
  • 复杂度分析

C++二叉树剪枝

题目链接

LCR 047. 二叉树剪枝 - 力扣(LeetCode)

题目描述

给定一个二叉树 根节点 root ,树的每个节点的值要么是 0,要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。

节点 node 的子树为 node 本身,以及所有 node 的后代。

解题思路

首先我们分为三步

①函数头

首先我们应该想到我们去递归解答这道题目,函数的参数非常好确认就是TreeNode* root即可。

函数的返回值:根据题目的意思我们要将那些全零的子树全部在树中删除,那么我们最好是返回一个TreeNode*即可。

②函数体

我们要实现的肯定是一个深度优先遍历dfs,那么

(1)dfs(root->left);

(2)dfs(root->right);

(3) 处理当前root

③截止条件

当我们深度历到root == nullptr为空的时候

代码

class Solution {
public:TreeNode* pruneTree(TreeNode* root) {if(root == nullptr)return nullptr;root->left =  pruneTree(root->left);root->right = pruneTree(root->right);if(root->left == nullptr && root->right == nullptr && root->val == 0)root = nullptr;return root;}
}

复杂度分析

时间复杂度:

dfs时间复杂度为O(N);

空间复杂度:

未使用额外的空间,空间复杂度为:O(1);

相关文章:

C++二叉树剪枝

文章目录 C二叉树剪枝题目链接题目描述解题思路代码复杂度分析 C二叉树剪枝 题目链接 LCR 047. 二叉树剪枝 - 力扣(LeetCode) 题目描述 给定一个二叉树 根节点 root ,树的每个节点的值要么是 0,要么是 1。请剪除该二叉树中所有节…...

ZooKeeper中节点的操作命令(查看、创建、删除节点)

天行健,君子以自强不息;地势坤,君子以厚德载物。 每个人都有惰性,但不断学习是好好生活的根本,共勉! 文章均为学习整理笔记,分享记录为主,如有错误请指正,共同学习进步。…...

el-table多选表格 实现默认选中 删除选中列表取消勾选等联动效果

实现效果如下&#xff1a; 代码如下&#xff1a; <template><div><el-tableref"multipleTable":data"tableData"tooltip-effect"dark"style"width: 100%"selection-change"handleSelectionChange"><…...

预安装win11的电脑怎么退回正版win10?

对于新购的笔记本 通常来讲预装的系统是全新安装的&#xff0c;是没有之前Windows10系统文件的&#xff0c;无法回退。 可以打开设置-----系统----恢复-----看下是否有该选项。 ------------------------------------------------------------------------------- 若是在上述…...

MATLAB——多层小波的重构

%% 学习目标&#xff1a;多层小波的重构 %% 程序1 clear all; close all; load noissin.mat; xnoissin; [C,L]wavedec(x,3,db1); %小波多层分解 ywaverec(C,L,db1); %重构&#xff0c;必须小波类型一致 emax(abs(x-y)) %重构的误差 %% 程序2 clear all;…...

解锁高效创作艺术!AI助力文章生成与精美插图搭配完美融合

在当今这个信息爆炸的时代&#xff0c;高效创作文章已经成为了一种必备的技能。然而&#xff0c;创作一篇高质量的文章并插入精美插图&#xff0c;往往需要耗费大量的时间和精力。现在&#xff0c;随着AI技术的发展&#xff0c;我们迎来了一个全新的文章创作时代——利用AI高效…...

✔ ★【备战实习(面经+项目+算法)】 10.29学习

✔ ★【备战实习&#xff08;面经项目算法&#xff09;】 坚持完成每天必做如何找到好工作1. 科学的学习方法&#xff08;专注&#xff01;效率&#xff01;记忆&#xff01;心流&#xff01;&#xff09;2. 每天认真完成必做项&#xff0c;踏实学习技术 认真完成每天必做&…...

微服务-Ribbon负载均衡

文章目录 负载均衡原理流程原理源码分析负载均衡流程 负载均衡策略饥饿加载总结 负载均衡原理 流程 原理 LoadBalanced 标记RestTemplate发起的http请求要被Ribbon进行拦截和处理 源码分析 ctrlshiftN搜索LoadBalancerInterceptor&#xff0c;进入。发现实现了ClientHttpRequ…...

UC3845BD1R2G一款专门针对离线和 DC-DC 转换器应用 高性能电流模式PWM控制器

UC3845BD1R2G为高性能固定频率电流模式控制器。专门针对离线和 DC-DC 转换器应用而设计&#xff0c;提供了外部部件极少的成本高效方案。这些集成电路具有振荡器、温度补偿参考、高增益误差放大器、电流传感比较器和高电流图腾柱输出&#xff0c;适用于驱动功率 MOSFET。还包括…...

vivo自研AI大模型即将问世,智能手机行业加速迈向AI时代

当前&#xff0c;以大模型为代表的人工智能技术已发展为新一轮科技革命和产业变革的重要驱动力量&#xff0c;被视作推动经济社会发展的关键增长极。 AI大模型潮起&#xff0c;千行百业走向百舸争流的AI创新应用期&#xff0c;前沿信息技术向手机、PC、车机等消费级终端加速渗…...

探索JavaScript事件流:DOM中的神奇旅程

&#x1f3ac; 江城开朗的豌豆&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! 目录 引言 1. 事件流的发展流程 1.1 传统的DOM0级事件 1.2 DOM2级事件和addEventListener方法 1.3 W3C DOM3级…...

听GPT 讲Rust源代码--library/std(8)

题图来自Why is Rust programming language so popular?[1] File: rust/library/std/src/sys/sgx/abi/reloc.rs 在Rust源代码中&#xff0c;sgx/abi/reloc.rs文件的作用是定义了针对Intel Software Guard Extensions (SGX)的重定位相关结构和函数。 该文件中的Rela 结构定义了…...

Hbase基本使用,读写原理,性能优化学习

文章目录 HBase简介HBase定义HBase数据模型**HBase** **逻辑结构****HBase** **物理存储结构****HBase** **基本架构** HBase 入门**HBase** **安装部署****HBase** 配置文件**HBase** 启动停止**HBase** **访问页面****HBase** **高可用****HBase Shell****HBase API**HBaseCo…...

添加主仓库后报错error: remote upstream already exists.

可能的原因 远程名 upstream 已经被使用&#xff1a; 这通常意味着你在之前已经添加了一个名为 upstream 的远程仓库。 解决方案 检查现有的远程仓库&#xff1a; 运行 git remote -v 来查看所有配置的远程仓库。这个命令会列出所有远程仓库的URL&#xff0c;你可以检查是否已…...

香港服务器如何做负载均衡?

​  在现代互联网时代&#xff0c;随着网站访问量的不断增加&#xff0c;服务器的负载也越来越重。为了提高网站的性能和可用性&#xff0c;负载均衡成为了一种常见的解决方案。 什么是负载均衡? 负载均衡是一种技术解决方案&#xff0c;用于在多个服务器之间分配负载&#…...

前端 :用HTML , CSS ,JS 做一个秒表

1.HTML&#xff1a; <body><div id "content"><div id "top"><div id"time">00:00:000</div></div><div id "bottom"><div id "btn_start">开始</div><div …...

BIOS MBR UEFI GPT详解

先来看下名词 启动方式&#xff1a; BIOS&#xff1a;Basic Input Output System&#xff0c;中文名称"基本输入输出系统"。 UEFI&#xff1a;Unified Extensible Firmware Interface&#xff0c;中文名称"统一的可扩展固件接口"。 Legacy&#xff1a;…...

2023NOIP A层联测20-点餐

一家新的餐馆开业了&#xff0c;为了吸引更多的顾客&#xff0c;每样餐品都有打折的活动。特别的&#xff0c;餐馆内一共有&#x1d45b;样菜品&#xff0c;编号从 1 1 1 到 n n n&#xff0c;每样菜品每人最多只能点一次。对于第 i i i 种菜品&#xff0c;其包含两种价格&a…...

3D LUT 滤镜 shader 源码分析

最近在做滤镜相关的渲染学习&#xff0c;目前大部分 LUT 滤镜代码实现都是参考由 GPUImage 提供的 LookupFilter 的逻辑&#xff0c;整个代码实现不多。参考网上的博文也有各种解释&#xff0c;参考了大量博文之后终于理解了&#xff0c;所以自己重新整理了一份&#xff0c;方便…...

五分钟理解Java跨平台原理(适合小白)

JVM通俗的理解 Java语言的一个非常重要的特点就是与平台的无关性。而使用Java虚拟机&#xff0c;即JVM&#xff08;Java Virtual Machine&#xff09;是实现这一特点的关键。JVM是一种用于计算设备的规范&#xff0c;它是一个虚构出来的计算机&#xff0c;是通过在实际的计算机…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...