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

代码随想录day18

513.找树左下角的值

本题用前中后序都可以(都是先遍历左再遍历右,保证最后一定是左侧的节点),因为没有中节点的处理逻辑,用全局变量记录最大深度,只要遇到叶子结点并且当前深度比最大深度大,就更新,同时用到了回溯。

深度最大的叶子结点是最后一行。左侧的节点不一定是左孩子。

class Solution {
public:int maxDepth=0;int res;void traversal(TreeNode* node,int depth){if(node->left==NULL&&!node->right&&depth>maxDepth){maxDepth=depth;res=node->val;}if(node->left){depth++;traversal(node->left,depth);depth--;}if(node->right){depth++;traversal(node->right,depth);depth--;}}int findBottomLeftValue(TreeNode* root) {traversal(root,1);return res;}
};

迭代法:(层序遍历)

用每一层的第一个元素更新结果值res,最后返回的就是最后一层第一个元素。每次循环,队列都要一边弹出元素一边加入元素。

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if(root) que.push(root);int res;while(!que.empty()){//先记录当前层的元素个数int size=que.size();for(int i=0;i<size;i++){TreeNode* node=que.front();que.pop();if(i==0) res=node->val;if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return res;}
};

112. 路径总和 

也是前中后序都可以,不存在中节点的处理逻辑。代码中有两处返回false的逻辑,第一处是单条路径不符合的话,返回false,第二处是如果所有的路径尝试后都没有返回true的话,就返回false。注意传入下层递归函数的值是已经减去节点后的值。

class Solution {
public:bool traversal(TreeNode* node,int curSum){if(!node->left&&!node->right&&curSum==0) return true;else if(!node->left&&!node->right&&curSum!=0) return false;//以上两个返回信息仅用于递归时if(node->left){curSum-=node->left->val;if(traversal(node->left,curSum)) return true;//下面的孩子节点告诉当前节点存在路径,那就继续向上返回true的信息curSum+=node->left->val;}if(node->right){curSum-=node->right->val;if(traversal(node->right,curSum)) return true;curSum+=node->right->val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(!root) return false;return traversal(root,targetSum-root->val);}
};

113.路径总和ii

注意终止条件有两个,符合/不符合,然后注意在进行下一层递归之前path已经记录了节点的数值,传入递归函数的数也是减去后的数。

class Solution {
public:vector<vector<int>> res;vector<int> path;void traversal(TreeNode* node,int cursum){//终止条件有两个,一个是符合条件,一个是不符合条件if(!node->left&&!node->right&&cursum==0){res.push_back(path);return;}if(!node->left&&!node->right) return;if(node->left){path.push_back(node->left->val);cursum-=node->left->val;traversal(node->left,cursum);cursum+=node->left->val;path.pop_back();}if(node->right){path.push_back(node->right->val);cursum-=node->right->val;traversal(node->right,cursum);cursum+=node->right->val;path.pop_back();}}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {res.clear();path.clear();if(!root) return res;path.push_back(root->val);traversal(root,targetSum-root->val);return res;}
};

106.从中序与后序遍历序列构造二叉树 

1、如果后序数组的元素个数为0,则返回NULL

2、如果不为空,取后序数组最后一个元素为根节点的值

3、找到后序数组最后一个元素在中序数组中的位置

4、切中序数组

5、切后序数组

6、递归构造二叉树

class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(postorder.size()==0) return NULL;//如果不为空,取后序数组最后一个元素为节点元素int rootval=postorder[postorder.size()-1];TreeNode* root=new TreeNode(rootval);if(postorder.size()==1) return root;//找后序数组最后一个元素在中序数组中的位置,作为切割点int idx;for(idx=0;idx<inorder.size();idx++){if(inorder[idx]==rootval) break;}//切中序数组vector<int> leftinorder(inorder.begin(),inorder.begin()+idx);vector<int> rightinorder(inorder.begin()+idx+1,inorder.end());//切后序数组postorder.resize(postorder.size()-1);vector<int> leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());vector<int> rightpostorder(postorder.begin()+leftinorder.size(),postorder.end());root->left=buildTree(leftinorder,leftpostorder);root->right=buildTree(rightinorder,rightpostorder);return root;}
};

105.从前序与中序遍历序列构造二叉树

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==0) return NULL;int rootval=preorder[0];TreeNode* root=new TreeNode(rootval);if(preorder.size()==1) return root;int index;for(index=0;index<inorder.size();index++){if(inorder[index]==preorder[0]) break;}vector<int> leftinorder(inorder.begin(),inorder.begin()+index);vector<int> rightinorder(inorder.begin()+index+1,inorder.end());vector<int> leftpreorder(preorder.begin()+1,preorder.begin()+leftinorder.size()+1);vector<int> rightpreorder(preorder.begin()+leftinorder.size()+1,preorder.end());root->left=buildTree(leftpreorder,leftinorder);root->right=buildTree(rightpreorder,rightinorder);return root;}
};

划分左中序区间的时候边界问题出错。

相关文章:

代码随想录day18

513.找树左下角的值 本题用前中后序都可以&#xff08;都是先遍历左再遍历右&#xff0c;保证最后一定是左侧的节点&#xff09;&#xff0c;因为没有中节点的处理逻辑&#xff0c;用全局变量记录最大深度&#xff0c;只要遇到叶子结点并且当前深度比最大深度大&#xff0c;就更…...

QT+OpenGL高级光照 Blinn-Phong和Gamma校正

QTOpenGL高级光照1 本篇完整工程见gitee:QtOpenGL 对应点的tag&#xff0c;由turbolove提供技术支持&#xff0c;您可以关注博主或者私信博主 Blinn-Phong 冯氏光照&#xff1a;视线与反射方向之间的夹角不小于90度&#xff0c;镜面光分量会变成0.0&#xff08;不是很合理&am…...

【Ubuntu系统内核更新与卸载】

【Ubuntu系统内核更新与卸载】 1. 前言2. 内核安装2.1 系统更新2.2 官网下载 3. 内核卸载3.1 需求分析3.2 卸载方法 1. 前言 我们在搭建环境时常常遇到内核版本不匹配的问题&#xff0c;需要我们安装新的内核版本&#xff1b;有时又会遇到在安装软件时报错boot空间已满无法安装…...

RL - 强化学习 马尔可夫奖励过程 (MRP) 的状态价值

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://blog.csdn.net/caroline_wendy/article/details/131084795 GitHub 源码: https://github.com/SpikeKing/Reinforcement-Learning-Algorithm 马尔可夫奖励过程 (MRP) 的状态价值是指在某…...

Mybatis之批处理流式查询

文章目录 1 批处理查询1.1 引言1.2 流式查询1.2.1 定义1.2.2 流式查询接口1.2.3 使用流式查询关闭问题1.2.3.1 SqlSessionFactory1.2.3.2 TransactionTemplate1.2.3.3 Transactional 注解 1.2.4 完整示例1.2.4.1 mapper接口和SQL1.2.4.2 Service操作 1.3 游标查询1.3.1 定义1.3…...

Spring架构篇--2.7.3 远程通信基础--Netty原理--bind实现端口的绑定

前言&#xff1a;在对ServerBootstrap 进行属性赋值之后&#xff0c;通过bind 方法完成端口的绑定&#xff0c;并开始在NioEventLoop中进行轮询进行事件的处理&#xff1b;本文主要探究ServersocketChannel 在netty 中是如何完成注册&#xff0c;以及端口的绑定 1 Nio selecto…...

【改进的多同步挤压变换】基于改进多同步挤压的高分辨率时频分析工具,用于分析非平稳信号(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

有关 python 切片的趣事

哈喽大家好&#xff0c;我是咸鱼 今天来讲一个我在实现 python 列表切片时遇到的趣事 在正式开始之前&#xff0c;我们先来了解一下切片&#xff08;slice&#xff09; 切片操作是访问序列&#xff08;列表、字符串…&#xff09;中元素的另一种方法&#xff0c;它可以访问一…...

ChatGPT 会带来失业潮吗?

&#xff08;永久免费&#xff0c;扫码加入&#xff09; 最近在翻知乎上的一些文章&#xff0c;很多都是跟ChatGPT有关的。因为本身是搞Python编程的&#xff0c;知乎推荐系统给我推荐了一篇廖雪峰老师的文章&#xff0c;觉得很有意思。 一共1119个赞&#xff0c;还是很厉害的&…...

如何对待工作中的失误

在日复一日的工作中&#xff0c;我们免不了会产生一些失误&#xff0c;会因此感到沮丧和失望。但如何正确地对待和处理这些失误才是最重要的&#xff0c;它直接影响到我们的工作表现和个人成长。一起来谈谈作为职场人的你时如何处理工作中的失误的吧&#xff01; 一、在面对失…...

微信小程序快速入门【一】

微信小程序快速入门【一】 文章目录 微信小程序快速入门【一】&#x1f468;‍&#x1f3eb;内容1&#xff1a;背景&#x1f468;‍⚖️内容2&#xff1a;准备工作&#x1f468;‍&#x1f4bb;内容3&#xff1a;新建一个小程序&#x1f349;文末推荐 &#x1f468;‍&#x1f…...

TiDB亿级数据亚秒响应查询集群部署

目录 1 集群部署1.1 环境要求1.1.1 操作系统建议配置1.1.2 服务器建议配置 1.2 环境准备1.3 安装TiUP1.3.1 什么是TiUP1.3.2 安装TiUP组件1.3.3 配置TiUP环境1.3.4 检查TiUP 工具是否安装1.3.5 安装 cluster 组件1.3.6 升级cluster组件 1.4 编辑部署文件1.4.1 常见的部署场景1.…...

并发——同步访问共享的可变数据

关键字 synchronized 可以保证在同一时刻&#xff0c;只有一个线程可以执行某一个方法&#xff0c;或者某一段代码块。许多程序员把同步的概念仅仅理解为一种互斥的方式。即&#xff0c;当一个对象被一个线程修改的时候&#xff0c;可以阻止另一个线程观察到内部不一致的状态。…...

Docker网络模型(九)禁用容器网络

禁用容器网络 如果你想完全禁用容器上的协议栈&#xff0c;你可以在启动容器时使用 --network none 标志。在容器内&#xff0c;只有回环设备被创建。下面的例子说明了这一点。 创建容器 $ docker run --rm -dit \--network none \--name no-net-alpine \alpine:latest \ash通…...

JavaScript 教程---互联网文档计划

学习目标&#xff1a; 每天记录一章笔记 学习内容&#xff1a; JavaScript 教程---互联网文档计划 笔记时间&#xff1a; 2023-6-5 --- 2023-6-11 学习产出&#xff1a; 1.入门篇 1、JavaScript 的核心语法包含部分 基本语法标准库宿主API 基本语法&#xff1a;比如操作符…...

做好功能测试需要的8项基本技能【点工进来】

功能测试是测试工程师的基础功&#xff0c;很多人功能测试还做不好&#xff0c;就想去做性能测试、自动化测试。很多人对功能测试的理解就是点点点&#xff0c;如何自己不用心去悟&#xff0c;去研究&#xff0c;那么你的职业生涯也就停留在点点点上了。在这里&#xff0c;我把…...

在弹出框内三个元素做水平显示

最终效果图要求是这样&#xff1a; js代码&#xff1a; // 显示弹出窗口 function showPopup(node) {var popup document.createElement(div);popup.className popup;var inputContainer1 document.createElement(div);/* inputContainer1.className input-container1; */…...

纠删码技术在vivo存储系统的演进【上篇】

作者&#xff1a;vivo 互联网服务器团队- Gong Bing 本文将学术界和工业界的纠删码技术的核心研究成果进行了相应的梳理&#xff0c;然后针对公司线上存储系统的纠删码进行分析&#xff0c;结合互联网企业通用的IDC资源、服务器资源、网络资源、业务特性进行分析对原有纠删码技…...

如何实现APP自动化测试?

APP测试&#xff0c;尤其是APP的自动化测试&#xff0c;在软件测试工程师的面试中越来越会被问到了。为了更好的回答这个问题&#xff0c;我今天就给大家分享一下&#xff0c;如何进行APP的自动化测试。 一、为了实现JavaAppiumJunit技术用于APP自动化测试&#xff0c;所以需要…...

​​INNODB和MyISAM区别

1 存储引擎是MyISAM 如下&#xff1a; CREATE table test_myisam (cli int ) ENGINEMyISAM 存储目录里会有三个文件 test_myisam.frm为“表定义”&#xff0c;是描述数据表结构的文件 test_myisam.MYI文件是表的索引 test_myisam.MYD文件是表的数据 2 存储引擎是INNODB…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...