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

【算法day13】二叉树:递归与回溯

题目引用


  1. 找树左下角的值
  2. 路径总和
  3. 从中序与后序遍历构造二叉树

今天就简简单单三道题吧~

1. 找到树左下角的值


给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:
在这里插入图片描述
输入: root = [2,1,3]
输出: 1

我们来分析一下题目,最底层的叶子节点,所以我们要求出树的深度,并且进行判断他是否到达底层。首先我们定义一个全局变量res和全局变量maxDep来记录递归过程中更深的节点和更深节点的值。然后我们判断当前节点有没有左右孩子节点,如果有我们递归进那个节点并更新resmaxDep,同时定义局部变量depth将其++后传进下一层,当其操作完返回这一层时将depth--,用作向右孩子递归的参数。而这个过程就叫做回溯。
我们来看代码

int res;int maxDep=INT_MIN;void travisal(TreeNode* root,int depth){if(root->left==NULL&&root->right==NULL){if(depth>maxDep){maxDep=depth;res=root->val;}return;}if(root->left){depth++;travisal(root->left,depth);depth--;}if(root->right){depth++;travisal(root->right,depth);depth--;}}int findBottomLeftValue(TreeNode* root) {travisal(root,0);return res;}

2.路径总和


给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点。

示例 1:
在这里插入图片描述
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。

我们来看题目,这道题其实知道了原理就和上道题大差不差了。上一道题目是找到最底层的节点的值,而这一道题目是找到一条相加为0的路径,两道题目都需要我们在二叉树中一层一层的寻找符合条件的节点并且返回它,那么我们是不是不难写出这样的模版

看情况返回类型 traversal(TreeNode* root,//第二变量用于判断){//对每一个节点要做的操作if(root->left){//增加条件//递归左边//减少条件}if(root->right){//增加条件//递归右边//减少条件}//考虑是否返回}

那么我们在这道题就将相加改为一开始就有一个变量等于targetSum,逐层减去每个节点的val,一旦==0,就返回true
来看代码:

bool traversal(TreeNode* root,int count){if(!root->left&&!root->right&&count==0) return true;if(!root->left&&!root->right) return false;if(root->left){count-=root->left->val;if(traversal(root->left,count)) return true;count+=root->left->val;}if(root->right){count-=root->right->val;if(traversal(root->right,count)) return true;count+=root->right->val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root==NULL) return false;return traversal(root,targetSum-root->val);}

大家看,一旦我们整理出规律,是不是这类题目我们只要考虑细节条件就能迎刃而解呢?

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


给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

示例 1:
在这里插入图片描述
输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

这道题目我们在学习数据结构时就做过,现在只要模拟过程就能解决啦。直接看代码

TreeNode* traversal(vector<int>& inorder,vector<int>& postorder){if(postorder.size()==0) return NULL;int rootValue=postorder[postorder.size()-1];TreeNode* root=new TreeNode(rootValue);if(postorder.size()==1) return root;int delimitIndex;for(delimitIndex=0;delimitIndex<inorder.size();delimitIndex++){if(inorder[delimitIndex]==rootValue) break;}vector<int> leftInorder(inorder.begin(),inorder.begin()+delimitIndex);vector<int> rightInorder(inorder.begin()+delimitIndex+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=traversal(leftInorder,leftPostorder);root->right=traversal(rightInorder,rightPostorder);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;return traversal(inorder, postorder);}

总结


今天的题目其实就是昨天的拓展与提升,大家务必将昨天的消化了再来做今天的题目。

相关文章:

【算法day13】二叉树:递归与回溯

题目引用 找树左下角的值路径总和从中序与后序遍历构造二叉树 今天就简简单单三道题吧~ 1. 找到树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 我们…...

上海亚商投顾:创业板指缩量下跌 多只高位股午后跌停

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 市场全天震荡调整&#xff0c;创业板指领跌&#xff0c;高位股开始出现退潮&#xff0c;建设工业、星光股份、…...

单步调试Android Framework——App冷启动

纸上得来终觉浅&#xff0c;绝知此事要躬行。 —— [宋]陆游 基于aosp_cf_x86_64_phone-trunk_staging-eng &#xff0c; 下面是具体断点位置。 第一部分&#xff0c;桌面launcher进程 com.android.launcher3.touch.ItemClickHandler onClickonClickAppShortcutstartAppShor…...

统计一个目录下的文件及目录数量-linux010

要统计一个目录下的文件数量&#xff08;包括子目录中的文件&#xff09;&#xff0c;可以使用以下命令&#xff1a; 1. 统计所有文件数量&#xff08;包括子目录&#xff09; 在终端中运行以下命令&#xff1a; find /path/to/directory -type f | wc -l 解释&#xff1a;…...

spring RestTemplate使用说明

rest-template是spring对httpclient的逻辑封装&#xff0c;它底层还是基于httpclient&#xff0c;所以一些配置其实跟httpclient是强相关的。 基本配置 rest-template可以不带参数&#xff0c;使用默认配置&#xff0c;也可以指定ClientHttpRequestFactory参数&#xff0c;Cl…...

thinkphp:try-catch捕获异常

使用简单的例子&#xff0c;实现了一个简单的try-catch捕获异常的实例 //开始事务Db::startTrans(); try{ //有异常抛出异常 if(存在错误){ throw new \Exception("异常信息"); } // 提交事务 Db::commit(); // 返回成功信息 ... } catch (\…...

shardingsphere分库分表跨库访问 添加分片规则

shardingsphere分库分表跨库访问 添加分片规则 建立 JDBC 环境 创建表 t_order&#xff1a; CREATE TABLE t_order (tid bigint(20) NOT NULL,tname varchar(255) DEFAULT NULL,goods_id bigint(20) DEFAULT NULL,tstatus varchar(255) DEFAULT NULL,PRIMARY KEY (tid) ) E…...

c++:std::map下标运算符的不合理使用

这是我分析之前遗留代码时发现的一个隐藏点&#xff1b;不过我并不认为这样使用std::map是合理的。 看看简化后的代码&#xff0c;v1、v2的值应该是多少呢&#xff1f; #include <map>std::map<int, int> cm[2];int get_cm_value(int device, int ctrl) { auto …...

KeyFormer:使用注意力分数压缩KV缓存

Keyformer: KV Cache Reduction through Key Tokens Selection for Efficient Generative Inference 202403&#xff0c;发表在Mlsys Introduction 优化KV cache的策略&#xff0c;主要是集中在系统级别的优化上&#xff0c;比如FlashAttention、PagedAttention&#xff0c;它…...

MetaGPT源码 (ContextMixin 类)

目录 理解 ContextMixin什么是 ContextMixin&#xff1f;主要组件实现细节 测试 ContextMixin示例&#xff1a;ModelX1. 配置优先级2. 多继承3. 多继承重写4. 配置优先级 在本文中&#xff0c;我们将探索 ContextMixin 类&#xff0c;它在多重继承场景中的集成及其在 Python 配…...

MATLAB生成.exe独立程序过程(常见问题解决方法)(2024.12.14)

本文只记录我执行过程中遇到的关键问题、以及解决方法&#xff0c;不讲诉整个流程。 电脑环境 win11系统 matlab 2024b 版本 整体流程 1.下载matlab运行时库,简写为MCR 2.配置MCR环境 3.打包程序 4.目标机器安装程序 一、下载MCR 下载这个折腾了大半天&#xff0c;大概问题就是…...

PHP排序算法:数组内有A~E,A移到C或者C移到B后排序,还按原顺序排序,循环

效果 PHP代码 public function demo($params){function moveNext($arr){$length count($arr);$lastElement $arr[$length - 1];for ($i $length - 1; $i > 0; $i--) {$arr[$i] $arr[$i - 1];}$arr[0] $lastElement;return $arr;}function moveAndReplace($array, $from…...

ChatGPT搜索全新升级,向全体用户开放,近屿智能助力AI行业发展

12月17日&#xff0c;OpenAI在第八天直播中正式宣布ChatGPT搜索功能全面升级&#xff0c;并即日起对所有ChatGPT用户开放。此次更新不仅带来了显著的性能提升&#xff0c;还引入了多项突破性功能&#xff0c;如更快的搜索速度、全新的地图体验以及YouTube视频嵌入&#xff0c;为…...

win10配置免密ssh登录远程的ubuntu

为了在终端ssh远程和使用VScode远程我的VM上的ubuntu不需要设置密码&#xff0c;需要在win10配置免密ssh登录远程的ubuntu。 在win10打开cmd&#xff0c;执行下面的代码生成密钥对&#xff08;会提示进行设置&#xff0c;按照默认的配置就行&#xff0c;一直回车&#xff09;&…...

skywalking 搭建 备忘录

基础环境 apache-skywalking-apm-9.6.0.tar.gz apache-skywalking-java-agent-9.1.0.tgz elasticsearch 7.14.1 采用dockers搭建 或者手动部署 kibana 可视化 应用 微服务版 consumer.jar eureka.jar 注册中心 provider.jar skywalking 地址 https://skywalkin…...

linux日常常用命令(AI向)

进程挂后台运行 nohup sh ./scripts/*****.sh > ./output/*****.log 2>&1 &删除***用户的所有python进程 pkill -u *** -f "^python"列出“***”用户的进程信息 ps aux --sort-%mem | grep ^***git add ./*git commit -m "注释"git push …...

信奥赛CSP-J复赛集训(bfs专题)(5):洛谷P3395:路障

信奥赛CSP-J复赛集训(bfs专题-刷题题单及题解)(5):洛谷P3395:路障 题目描述 B 君站在一个 n n n\times n n...

《红队和蓝队在网络安全中的定义与分工》

网络安全中什么是红队蓝队 在网络安全领域&#xff0c;红队和蓝队是一种对抗性的演练机制&#xff0c;用于测试和提升网络安全防御能力。 红队&#xff08;Red Team&#xff09; 定义与目标 红队是扮演攻击者角色的团队。他们的主要任务是模拟真实的网络攻击&#xff0c;利用各…...

李宏毅深度强化学习入门笔记:PPO

李宏毅-深度强化学习-入门笔记&#xff1a;PPO 一、Policy Gradient&#xff08;一&#xff09;基本元素&#xff08;二&#xff09;Policy of Actor1. Policy π \pi π 是带有参数 θ \theta θ 的 network2. 例子&#xff1a;运行流程 &#xff08;三&#xff09;Actor, E…...

vue2项目中如何把rem设置为固定的100px

在 Vue 2 项目中&#xff0c;可以通过动态设置 html 元素的 font-size 来将 1rem 固定为 100px。以下是具体步骤&#xff1a; 在项目的入口文件 main.js 中添加以下代码&#xff0c;用于动态设置 html 的 font-size&#xff1a; // main.js function setHtmlFontSize() {cons…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...