代码随想录刷题随记15-二叉树回溯
代码随想录刷题随记15-二叉树回溯
110.平衡二叉树
leetcode链接
一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
求深度和求高度的区别:
求深度可以从上到下去查 所以需要前序遍历(中左右),而高度只能从下到上去查,所以只能后序遍历(左右中)
递归:
所以这里的递归其实是后序遍历的思路
class Solution {
public:void subjudge(bool & isbalanced,int&height ,TreeNode * root){if(root==nullptr){isbalanced=true;height=0;return;} int heightleft,heightright;bool ifleftb,ifrightb; subjudge(ifleftb, heightleft, root->left);subjudge(ifrightb, heightright, root->right);if((ifleftb &&ifrightb)&&(abs(heightleft-heightright)<=1))isbalanced=true;elseisbalanced=false;height=heightleft>heightright?heightleft+1:heightright+1;}bool isBalanced(TreeNode* root) {bool isbalanced;int height;subjudge(isbalanced,height,root);return isbalanced;}
};
此题用迭代法,其实效率很低,因为没有很好的模拟回溯的过程,所以迭代法有很多重复的计算。虽然理论上所有的递归都可以用迭代来实现,但是有的场景难度可能比较大。
例如:都知道回溯法其实就是递归,但是很少人用迭代的方式去实现回溯算法!
257. 二叉树的所有路径
leetcode链接
class Solution {
public:void sub(TreeNode* root,vector<int>&path,vector<string>& ret){if(root!=nullptr)path.push_back(root->val);if(root->left==nullptr&&root->right==nullptr){string tmp="";for(int i=0;i<path.size()-1;i++){tmp+=to_string(path[i]);tmp += "->";}tmp+=to_string(path[path.size()-1]);ret.push_back(tmp);return;}if(root->left!=nullptr){sub(root->left,path,ret);path.pop_back();//回溯}if(root->right!=nullptr){sub(root->right,path,ret);path.pop_back();//回溯}return;}vector<string> binaryTreePaths(TreeNode* root) {vector<string> ret;vector<int> path;if(root==nullptr)return {};sub(root,path,ret);return ret;}
};
迭代版本
404.左叶子之和
leetcode链接
class Solution {
public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> ret;stack<string> stackPath;stack<TreeNode*> stackNode;if(root==nullptr)return {};stackNode.push(root);stackPath.push("");while(!stackNode.empty()){TreeNode * cur=stackNode.top();stackNode.pop();string path=stackPath.top();stackPath.pop(); path+=to_string(cur->val); path+="->";if(cur->left==nullptr&&cur->right==nullptr){path.pop_back();path.pop_back();ret.push_back(path);}if(cur->left!=nullptr){stackNode.push(cur->left);stackPath.push(path);}if(cur->right!=nullptr){stackNode.push(cur->right);stackPath.push(path);} }return ret;}
};
404.左叶子之和
leetcode链接
当前节点没法判断自己是不是左叶子,必须要通过节点的父节点来判断其左孩子是不是左叶子。
判断代码如下:
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {左叶子节点处理逻辑
}
class Solution {
public:void sub(TreeNode * root,int& sum){if(root==nullptr)return;if(root->right!=nullptr){sub(root->right,sum);}if(root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr){sum+=root->left->val;return;}if(root->left!=nullptr){sub(root->left,sum);} }int sumOfLeftLeaves(TreeNode* root) {int sum=0;sub(root,sum);return sum;}
};
迭代法
本题迭代法使用前中后序都是可以的,只要把左叶子节点统计出来,就可以了
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {int sum=0;stack<TreeNode*>mystack;if(root==nullptr)return 0;mystack.push(root);while(!mystack.empty()){TreeNode * cur=mystack.top();mystack.pop();if(cur->right!=nullptr){mystack.push(cur->right);}if(cur->left!=nullptr&&cur->left->left==nullptr&&cur->left->right==nullptr){sum+=cur->left->val;continue;}if(cur->left!=nullptr){mystack.push(cur->left);}}return sum;}
};
相关文章:
代码随想录刷题随记15-二叉树回溯
代码随想录刷题随记15-二叉树回溯 110.平衡二叉树 leetcode链接 一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 求深度和求高度的区别: 求深度可以从上到下去查 所以需要前序遍历(中左右ÿ…...

基于SpringBoot Vue养老院管理
一、📝功能介绍 基于SpringBoot Vue养老院管理 角色:管理员、企业、老人子女、老人 管理员:管理员登录进入养老院管理系统可以对系统首页、个人中心、服务人员管理、老人管理、老人子女管理、老人档案管理、社区活动管理、活动记录管理、床…...
盘点编程方法论中的一些思想
背景 在日常编程开发中,虽然不同公司,业务不同,语言不同,但是工作久了,我们会发现一些编程思想几乎是不变的。这些编程思想,往往来自于大量实际问题场景的方法总结,可以很好的应对某一类问题。如…...
通过电机转速计算主轴旋转单圈所需时间(CODESYS ST代码)
1、伺服丝杠系统常用算法功能块 伺服丝杠系统常用算法功能块-CSDN博客文章浏览阅读353次。这篇博客主要介绍伺服、丝杠系统常用的运算功能块,其它相关运算可以查看下面文章链接:信捷PLC脉冲频率、位移、转速相关计算(C语言编程应用)_RXXW_Dor的博客-CSDN博客。https://rxxw-…...

多线程的入门(二)线程实现与初步使用
1.实现Runable接口 实现Runable接口,实现run方法; 这种方式创建的线程实现类执行时需要创建Thread实例去运行该任务 示例如下: package com.example.springbootdamo.Thread;import org.apache.logging.log4j.LogManager; import org.apach…...

数据结构(初阶)第二节:顺序表
数据结构(初阶)第一节:数据结构概论-CSDN博客 从本文正式进入对数据结构的讲解,开始前友友们要有C语言的基础,熟练掌握动态内存管理、结构体、指针等章节,方便后续的学习。 目录 顺序表(Sequen…...

鸿蒙OS元服务开发:【(Stage模型)设置应用主窗口】
一、设置应用主窗口说明 在Stage模型下,应用主窗口由UIAbility创建并维护生命周期。在UIAbility的onWindowStageCreate回调中,通过WindowStage获取应用主窗口,即可对其进行属性设置等操作。还可以在应用配置文件中设置应用主窗口的属性&…...

lua学习笔记6(经典问题输出99乘法表)
print("************for循环的99乘法表*************") for i 1, 9 dolocal line "" -- 创建一个局部变量来累积每行的输出--local 是一个关键字,用于声明一个局部变量。for j 1, i doline line .. j .. "*" .. i .. ""…...

物联网行业中,我们如何选择数据库?
在当今数字化潮流中,我们面对的不仅是海量数据,更是时间的涟漪。从生产线的传感器到金融市场的交易记录,时间序列数据成为了理解事物演变和趋势的关键。在面对这样庞大而动态的数据流时,我们需要深入了解一种强大的工具——时序数…...

openstack云计算(一)————openstack安装教程,创建空白虚拟机,虚拟机的环境准备
1、创建空白虚拟机 需要注意的步骤会截图一下,其它的基本都是下一步,默认的即可 ----------------------------------------------------------- 2、在所建的空白虚拟机上安装CentOS 7操作系统 (1)、在安装CentOS 7的启动界面中…...

Linux存储的基本管理
实验环境: 系统里添加两块硬盘 ##1.设备识别## 设备接入系统后都是以文件的形式存在 设备文件名称: SATA/SAS/USB /dev/sda,/dev/sdb ##s SATA, dDISK a第几块 IDE /dev/hd0,/dev/hd1 ##h hard VIRTIO-BLOCK /de…...
Python yield解析:深入理解生成器的魔力
Python中的yield关键字是生成器函数中非常重要的一部分,它可以使函数暂停执行并保存当前状态,同时允许生成器函数返回一个值。本文将详细介绍yield关键字的用法、特性、基本功能、高级功能、实际应用场景以及总结,帮助深入了解yield关键字的作…...
【Linux】GCCGDB
五、GCC & GDB 5.1 gcc 阶段变化命令预处理hello.c->hello.igcc -E 编译hello.i->hello.sgcc -S 汇编hello.s->hello.ogcc -c 链接hello.o->a.outgcc gcc -E hello.c -o 1.i # -o指定输出文件 gcc -E hello.c -g # -g包含提示信息 gcc -D gcc -DDebug <…...

InternLM2-Chat-1.8B 模型测试
在interStudio进行InternLM2-Chat-1.8B模型访问,进入开发机后 配置基础环境 新建conda环境并且进入 conda create -n demo python3.10 -y conda activate demo 下载pytorch等相关包 conda install pytorch2.0.1 torchvision0.15.2 torchaudio2.0.2 pytorch-cuda11.…...
Flutter 关键字
import ‘package:xxxx.dart’; //源于pub.dev (完美的相对引入) import ‘xxxx.dart’; //自定义文件(库)(参考的相对引入(填写import命令码所在文件的上级文件夹下的文件(库)相对路径))(受到import命令码所在文件的参考路径的影响) import:import不具有传递性(类似…...
Java常用API之Collections类解读
写在开头:本文用于作者学习Java常用API 我将官方文档中Collections类中所有API全测了一遍并打印了结果,日拱一卒,常看常新 addAll() 将所有指定元素添加到指定 collection 中 可以添加一个或多个元素 Testpublic void test_addAl…...

KV260 BOOT.BIN更新 ubuntu22.04 netplan修改IP
KV260 2022.2设置 BOOT.BIN升级 KV260开发板需要先更新BOOT.BIN到2022.2版本,命令如下: sudo xmutil bootfw_update -i “BOOT-k26-starter-kit-202305_2022.2.bin” 注意BOOT.BIN应包含全目录。下面是更新到2022.1 FW的示例,非更新到2022.…...

Android 代码自定义drawble文件实现View圆角背景
简介 相信大多数Android开发都会遇到一个场景,给TextView或Button添加背景颜色,修改圆角,描边等需求。一看到这样的实现效果,自然就是创建drawble文件,设置相关属性shap,color,radius等。然后将…...

C#实现Word文档转Markdown格式(Doc、Docx、RTF、XML、WPS等)
文档格式的多样性丰富了我们的信息交流手段,其中Word文档因其强大的功能性而广受欢迎。然而,在网络分享、版本控制、代码阅读及编写等方面,Markdown因其简洁、易于阅读和编辑的特性而展现出独特的优势。将Word文档转换为Markdown格式…...

信息系统架构设计-以服务为中心的企业整合实践
生命周期 业务分析服务建模架构设计系统开发 案例背景 某航空公司的信息系统已有好几十年的历史。该航空公司的主要业务系统构建于20世纪七八十年代,以IBM的主机系统为主。 近年来,该公司已经在几个主要的核心系统之间构建了用于信息集成的信息Hub(I…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...

ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...

iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...