当前位置: 首页 > 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;是通过在实际的计算机…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...