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

代码随想录刷题随记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链接 一棵高度平衡二叉树定义为&#xff1a;一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 求深度和求高度的区别&#xff1a; 求深度可以从上到下去查 所以需要前序遍历&#xff08;中左右&#xff…...

基于SpringBoot Vue养老院管理

一、&#x1f4dd;功能介绍 基于SpringBoot Vue养老院管理 角色&#xff1a;管理员、企业、老人子女、老人 管理员&#xff1a;管理员登录进入养老院管理系统可以对系统首页、个人中心、服务人员管理、老人管理、老人子女管理、老人档案管理、社区活动管理、活动记录管理、床…...

盘点编程方法论中的一些思想

背景 在日常编程开发中&#xff0c;虽然不同公司&#xff0c;业务不同&#xff0c;语言不同&#xff0c;但是工作久了&#xff0c;我们会发现一些编程思想几乎是不变的。这些编程思想&#xff0c;往往来自于大量实际问题场景的方法总结&#xff0c;可以很好的应对某一类问题。如…...

通过电机转速计算主轴旋转单圈所需时间(CODESYS ST代码)

1、伺服丝杠系统常用算法功能块 伺服丝杠系统常用算法功能块-CSDN博客文章浏览阅读353次。这篇博客主要介绍伺服、丝杠系统常用的运算功能块,其它相关运算可以查看下面文章链接:信捷PLC脉冲频率、位移、转速相关计算(C语言编程应用)_RXXW_Dor的博客-CSDN博客。https://rxxw-…...

多线程的入门(二)线程实现与初步使用

1.实现Runable接口 实现Runable接口&#xff0c;实现run方法&#xff1b; 这种方式创建的线程实现类执行时需要创建Thread实例去运行该任务 示例如下&#xff1a; package com.example.springbootdamo.Thread;import org.apache.logging.log4j.LogManager; import org.apach…...

数据结构(初阶)第二节:顺序表

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

鸿蒙OS元服务开发:【(Stage模型)设置应用主窗口】

一、设置应用主窗口说明 在Stage模型下&#xff0c;应用主窗口由UIAbility创建并维护生命周期。在UIAbility的onWindowStageCreate回调中&#xff0c;通过WindowStage获取应用主窗口&#xff0c;即可对其进行属性设置等操作。还可以在应用配置文件中设置应用主窗口的属性&…...

lua学习笔记6(经典问题输出99乘法表)

print("************for循环的99乘法表*************") for i 1, 9 dolocal line "" -- 创建一个局部变量来累积每行的输出--local 是一个关键字&#xff0c;用于声明一个局部变量。for j 1, i doline line .. j .. "*" .. i .. ""…...

物联网行业中,我们如何选择数据库?

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

openstack云计算(一)————openstack安装教程,创建空白虚拟机,虚拟机的环境准备

1、创建空白虚拟机 需要注意的步骤会截图一下&#xff0c;其它的基本都是下一步&#xff0c;默认的即可 ----------------------------------------------------------- 2、在所建的空白虚拟机上安装CentOS 7操作系统 &#xff08;1&#xff09;、在安装CentOS 7的启动界面中…...

Linux存储的基本管理

实验环境&#xff1a; 系统里添加两块硬盘 ##1.设备识别## 设备接入系统后都是以文件的形式存在 设备文件名称&#xff1a; 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关键字是生成器函数中非常重要的一部分&#xff0c;它可以使函数暂停执行并保存当前状态&#xff0c;同时允许生成器函数返回一个值。本文将详细介绍yield关键字的用法、特性、基本功能、高级功能、实际应用场景以及总结&#xff0c;帮助深入了解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模型访问&#xff0c;进入开发机后 配置基础环境 新建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&#xff1a;import不具有传递性(类似…...

Java常用API之Collections类解读

写在开头&#xff1a;本文用于作者学习Java常用API 我将官方文档中Collections类中所有API全测了一遍并打印了结果&#xff0c;日拱一卒&#xff0c;常看常新 addAll() 将所有指定元素添加到指定 collection 中 可以添加一个或多个元素 Testpublic void test_addAl…...

KV260 BOOT.BIN更新 ubuntu22.04 netplan修改IP

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

Android 代码自定义drawble文件实现View圆角背景

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

C#实现Word文档转Markdown格式(Doc、Docx、RTF、XML、WPS等)

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

信息系统架构设计-以服务为中心的企业整合实践

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

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

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

【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&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 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 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

自然语言处理——Transformer

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

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;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 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...