代码随想录刷题随记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…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...

【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...