当前位置: 首页 > 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…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

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.构…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...