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

代码随想录算法训练营Day18|513.找树左下角的值、112. 路径总和、113. 路径总和ii、106.从中序与后序遍历序列构造二叉树

目录

513.找树左下角的值

前言

层序遍历

递归法

112. 路径总和

前言

  递归法

113. 路径总和ii

前言

递归法

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

前言

思路

递归法

总结


513.找树左下角的值

题目链接

文章链接

前言

         本题要求得到二叉树最后一行最左边的值,使用层序遍历可以较为容易地实现,使用递归法要再次用到回溯对不满足条件的路径进行回退。

层序遍历

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;int result = 0;if (root == NULL) return result;que.push(root);vector <int> vec;while (!que.empty()){int size = que.size();vec = {}; //每层遍历都要初始化vec数组for (int i = 0; i < size; i++){TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result = vec[0];}
};

        因为最终只要获得最后一行的节点数值,所以vec容器每层都要重新初始化进行收集,直到最后一层,此时容器中保存的即为最后一行的节点数值,第一个就是符合条件的左下角的值。

递归法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth = INT_MIN;int result;void traversal(TreeNode* root, int depth){if (root->left == NULL && root->right == NULL){ //判断是否为叶子节点if (depth > maxDepth){maxDepth = depth;result = root->val;}return;}if (root->left){ //左depth++;traversal(root->left, depth);depth--; //回溯}if (root->right){ //右depth++;traversal(root->right,depth);depth--; //回溯}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};

         由于只需要求最下行最左侧节点,因此在递归遍历时不需要对中节点进行处理,满足最大深度的叶子节点和最左侧的条件才是符合题目要求的。

112. 路径总和

题目链接

文章链接

前言

        本题的目的在于更好地理解递归函数什么时候要有返回值,什么时候没有返回值。

        在确定递归函数的参数和返回类型时,参数需要二叉树的根节点,还需要一个计数器,这个计数器用来计算二叉树的一条边之和是否正好是目标和,计数器为int型。

        递归函数什么时候需要返回值?什么时候不需要返回值?这里总结如下三点:

  • 如果需要搜索整棵二叉树且不用处理递归返回值,递归函数就不要返回值。 
  • 如果需要搜索整棵二叉树且需要处理递归返回值,递归函数就需要返回值。
  • 如果要搜索其中一条符合条件的路径,那么递归一定需要返回值,因为遇到符合条件的路径了就要及时返回。

  递归法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool traversal(TreeNode* cur, int count){if (!cur->left && !cur->right && count == 0) return true;if (!cur->left && !cur->right) return false;if (cur->left){count -= cur->left->val;if (traversal(cur->left, count)) return true;count += cur->left->val; //回溯}if (cur->right){count -= cur->right->val;if (traversal(cur->right, count)) return true;count += cur->right->val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if (root == NULL) return false;return traversal(root, targetSum - root->val);}
};

        掌握本题后,下面一题就好理解了。 

113. 路径总和ii

题目链接

文章链接

前言

        路径总和ii要遍历整个树,找到所有路径,所以递归函数不要返回值!

递归法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:vector<vector<int>> result;vector<int> path;void traversal(TreeNode* cur, int count){if (!cur->left && !cur->right && count == 0){result.push_back(path);return;}if (!cur->left && !cur->right) return;if (cur->left){path.push_back(cur->left->val); count -= cur->left->val;traversal(cur->left, count);count += cur->left->val;path.pop_back();}if (cur->right){path.push_back(cur->right->val);count -= cur->right->val;traversal(cur->right, count);count += cur->right->val;path.pop_back();}return;}public:vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if (root == NULL) return result;path.push_back(root->val);traversal(root, targetSum - root->val);return result;}
};

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

题目链接

文章链接

前言

         本题要根据两个遍历顺序构造一个唯一的二叉树,整体思路是以后序数组的最后一个元素为切割点,先切中序数组,根据中序数组,反过来再切后序数组。一层一层切下去,每次后序数组最后一个元素就是节点元素。

思路

实现步骤:

  • 第一步:判断数组大小是否为零,为零说明是空节点了;

  • 第二步:如果不为零,那么取后序数组最后一个元素作为根节点元素;

  • 第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点;

  • 第四步:切割中序数组,切成中序左数组和中序右数组 ;

  • 第五步:切割后序数组,切成后序左数组和后序右数组;

  • 第六步:递归处理左区间和右区间

递归法

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private: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 index;for (index = 0; index < inorder.size(); index++){if (inorder[index] == rootValue) break;} //第四步 切割中序数组 得到 中序左数组和中序右数组//左闭右开区间vector<int> leftInorder(inorder.begin(), inorder.begin() + index);vector<int> rightInorder(inorder.begin() + index + 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;}public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0) return NULL;return traversal(inorder, postorder);}
};

        要注意切割时边界值的判断。

总结

        重点掌握巩固二叉树的递归实现,以及二叉树递归参数及返回值的确定。

相关文章:

代码随想录算法训练营Day18|513.找树左下角的值、112. 路径总和、113. 路径总和ii、106.从中序与后序遍历序列构造二叉树

目录 513.找树左下角的值 前言 层序遍历 递归法 112. 路径总和 前言 递归法 113. 路径总和ii 前言 递归法 106.从中序与后序遍历序列构造二叉树 前言 思路 递归法 总结 513.找树左下角的值 题目链接 文章链接 前言 本题要求得到二叉树最后一行最左边的值&#xf…...

【蓝桥备赛】技能升级——二分查找

题目链接 技能升级 个人思路 需要给n个技能添加技能点&#xff0c;无论技能点加成如何衰减&#xff0c;每次始终都是选择当前技能加点加成最高的那一项技能&#xff0c;所以最后一次的加点一定也是加在当时技能攻击加成最高的那个。此时&#xff0c;我们去寻找最后一次的加点…...

zyqn-arm软中断设置

所有SGI都是边缘触发的&#xff0c;sgi的灵敏度类型是固定的&#xff0c;不能改变。 软中断初始化流程 1、初始化异常处理 2、初始化中断控制器 3、注册异常处理回调函数到CPU 4、连接软中断信号与注册软中断回调函数 5、使能中断控制器中的软中断中断 6、使能异常处理 …...

k8s---pod基础下

k8s的pod与docker重启策略的区别 k8s的重启策略 always deployment的yaml文件只能是always&#xff0c;pod的yaml三种模式都可以。不论正常退出还是非正常退出都重启。OnFailure&#xff1a;正常退出不重启&#xff0c;非正常退出会重启Never&#xff1a;正常退出和非正常退出…...

玩转朋友圈!这样运营朋友圈吸睛又吸金!

朋友圈已成为现代社交媒体中不可或缺的平台&#xff0c;并且有很大的潜力用于营销和推广。那么如何才能让朋友圈在众多用户中脱颖而出&#xff0c;吸引眼球并提升商业效益呢&#xff1f;主要从以下几点出发&#xff1a; 首先&#xff0c;要想吸引关注&#xff0c;您需要在朋友…...

react学习

目录 一、react基础 5.loadsh使用排序8.ref获取DOM对象10.props使用*13.UseEffect 二、 react使用redux三、美团外卖项目完成页面制作使用redux渲染页面使用react-router-dom评价 一、react基础 jsx 大括号的作用 {count} {userLlist.map((item)>{return <li key{item…...

vue-cli项目中vue.config.js的配置

vue-cli项目中vue.config.js的配置 一、直接上代码 一、直接上代码 let path require(path) let glob require(glob)function resolve(dir) {return path.join(__dirname, src/${dir}) }module.exports {pages: {index: {// page 的入口entry: src/main.js,// 模板来源temp…...

Github 2024-01-04 开源项目日报 Top10

根据Github Trendings的统计&#xff0c;今日(2024-01-04统计)共有10个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Python项目3C项目2TypeScript项目2Java项目2Jupyter Notebook项目1Go项目1 系统设计指南 创建周期&#xff…...

使用GPTs+Actions自动获取第三方数据

目录 安装插件与GPT对话联网插件首先,创建GPTs。 Voxscript 官网:https://voxscript.awt.icu/index.htmlOpenAI Schema:https://voxscript.awt.icu/swagger/v1/swagger.yamlServer URL: servers: url: https://voxscript.awt.icu安装插件 要使用这个插件&...

git提交操作(不包含初始化仓库)

1.进入到本地的git仓库 查看状态 git status 如果你之前有没有成功的提交&#xff0c;直接看第5步。 2.追踪文件 git add . 不要提交大于100M的文件&#xff0c;如果有&#xff0c;看第5步 3.提交评论 git commit -m "你想添加的评论" 4.push (push之前可以再…...

使用YOLOv8和Grad-CAM技术生成图像热图

目录 yolov8导航 YOLOv8&#xff08;附带各种任务详细说明链接&#xff09; 概述 环境准备 代码解读 导入库 定义letterbox函数 调整尺寸和比例 计算填充 应用填充 yolov8_heatmap类定义和初始化 后处理函数 绘制检测结果 类的调用函数 热图生成细节 参数解释 we…...

Vue: 多个el-select不能重复选择相同属性

一、场景 1.需求&#xff1a; 用户可自由选择需要修改的对象并同时修改多个属性&#xff0c;需要校验修改对象不能重复选择&#xff0c;但是可供修改属性是固定的 2.目标效果&#xff1a; 二、实现 1.主要代码&#xff1a; <template><el-selectv-model"se…...

金色麦芒的2023

2023年即将过去&#xff0c;回首这一年&#xff0c;我深感自己在技术和职业生涯中取得了巨大的进步。这一年里&#xff0c;我不仅在技术层面有了更深入的掌握&#xff0c;也在个人成长和职业规划上有了更明确的方向。 首先&#xff0c;在技术层面&#xff0c;我今年最大的收获是…...

java设计模式学习之【策略模式】

文章目录 引言策略模式简介定义与用途实现方式 使用场景优势与劣势在Spring框架中的应用计算示例代码地址 引言 设想你正在玩一个策略游戏&#xff0c;每一个决策都会导致不同的游戏结局。同样地&#xff0c;在软件开发中&#xff0c;我们常常需要根据不同的场景或条件选择不同…...

Mybatis SQL构建器类 - SqlBuilder and SelectBuilder (已经废弃)

在3.2版本之前&#xff0c;我们采用了一种略有不同的方法&#xff0c;通过利用ThreadLocal变量来掩盖一些使Java DSL有点繁琐的语言限制。然而&#xff0c;这种方法现在已被弃用&#xff0c;因为现代框架已经普及了使用构建器模式和匿名内部类的概念。因此&#xff0c;SelectBu…...

【Linux】不常用命令记录

查看开启的网络端口 1、使用netstat命令“netstat -tuln”&#xff0c;该命令将显示所有当前监听的TCP和UDP端口&#xff1b; 2、使用ss命令“ss -tuln”&#xff0c;用于显示当前监听的TCP和UDP端口&#xff1b; 3、使用lsof命令“lsof -i”&#xff0c;将显示当前打开的网络…...

【docker】安装docker环境并启动容器

一、安装docker 这里以centos系统为例安装docker环境 # 删除已有安装包 sudo yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-enginesudo yum install -y yum-utils # 设置源 y…...

AIOps探索 | 基于大模型构建高效的运维知识及智能问答平台(2)案例分享

原作者&#xff1a;擎创科技产品专家 布博士 案例分享 所需要的软件列表 本次案例的实现&#xff0c;全部采用开源或SAAS的产品来提供&#xff0c;并不涉及到私有化部署的软件产品。软件列表如下所示&#xff0c;如何申请apikey请自行研究&#xff0c;在这里不再详细说明&…...

【ESP32接入国产大模型之文心一言】

1. 怎样接入文心一言 随着人工智能技术的不断发展&#xff0c;自然语言处理领域也得到了广泛的关注和应用。在这个领域中&#xff0c;文心一言作为一款强大的自然语言处理工具&#xff0c;具有许多重要的应用价值。本文将重点介绍如何通过ESP32接入国产大模型之文心一言api&am…...

保湿剂,预计2026年市场规模将达到约230亿美元

全球市场分析 从全球市场来看&#xff0c;保湿剂市场规模正在快速增长。主要集中在欧美和亚太地区的市场&#xff0c;据市场调研机构的数据显示&#xff0c;预计2026年&#xff0c;全球保湿剂市场规模将达到约230亿美元。保湿剂的应用领域不断拓展&#xff0c;包括从化妆品到个…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

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

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

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...