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

代码随想录算法训练营第17天(二叉树5)| 找树左下角的值二叉树的路径总和从中序与后序遍历序列构造二叉树从前序与中序遍历序列构造二叉树

513.找树左下角的值

leetcode题目地址
题目链接/文章讲解/视频讲解

如果使用递归法,如何判断是最后一行:
其实就是深度最大的叶子节点一定是最后一行。

//迭代法
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result = 0;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (i == 0) result = node->val; // 记录最后一行第一个元素if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};//递归法
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) {traversal(root->left, depth + 1); // 隐藏着回溯,下一个遍历的时候深度加一,本层的不变}if (root->right) {traversal(root->right, depth + 1); // 隐藏着回溯, 下一个遍历的时候深度加一,本层的不变}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};

112. 路径总和

leetcodet题目链接
题目链接/文章讲解/视频讲解
因为终止条件是判断叶子节点,所以递归的过程中就不要让空节点进入递归了。
递归函数是有返回值的,如果递归函数返回true,说明找到了合适的路径,应该立刻返回。
左右子树递归时候的返回值要做判断,如果有一支返回true就可以提前返回结果,如果都没有返回true,返回false

class Solution {
private:bool traversal(TreeNode* cur, int count) {if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点,并且计数为0if (!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;}public:bool hasPathSum(TreeNode* root, int sum) {if (root == NULL) return false;return traversal(root, sum - root->val);}
};

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

106.从中序与后序遍历序列构造二叉树,105.从前序与中序遍历序列构造二叉树
leetcode题目链接
题目链接/文章讲解/视频讲解
说到一层一层切割,就应该想到了递归。
来看一下一共分几步:
第一步:如果数组大小为零的话,说明是空节点了。
第二步:如果不为空,那么取后序数组最后一个元素作为节点元素。
第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点
第四步:切割中序数组,切成中序左数组和中序右数组 (顺序别搞反了,一定是先切中序数组)
第五步:切割后序数组,切成后序左数组和后序右数组
第六步:递归处理左区间和右区间

//框架代码
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 delimiterIndex;for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 第四步:切割中序数组,得到 中序左数组和中序右数组// 第五步:切割后序数组,得到 后序左数组和后序右数组// 第六步root->left = traversal(中序左数组, 后序左数组);root->right = traversal(中序右数组, 后序右数组);return root;
}//完整代码
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 delimiterIndex;for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 切割中序数组// 左闭右开区间:[0, delimiterIndex)vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);// [delimiterIndex + 1, end)vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );// postorder 舍弃末尾元素postorder.resize(postorder.size() - 1);// 切割后序数组// 依然左闭右开,注意这里使用了左中序数组大小作为切割点// [0, leftInorder.size)vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());// [leftInorder.size(), end)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 || postorder.size() == 0) return NULL;return traversal(inorder, postorder);}
};

相关文章:

代码随想录算法训练营第17天(二叉树5)| 找树左下角的值二叉树的路径总和从中序与后序遍历序列构造二叉树从前序与中序遍历序列构造二叉树

513.找树左下角的值 leetcode题目地址 题目链接/文章讲解/视频讲解 如果使用递归法&#xff0c;如何判断是最后一行&#xff1a; 其实就是深度最大的叶子节点一定是最后一行。 //迭代法 class Solution { public:int findBottomLeftValue(TreeNode* root) {queue<TreeNod…...

代码随想录 Leetcode106. 从中序与后序遍历序列构造二叉树

题目&#xff1a; 代码&#xff08;首刷看解析 2024年1月30日&#xff09;&#xff1a; class Solution { public:TreeNode* recursion(vector<int>& inorder, vector<int>& postorder, int longthOfLeft, int longthOfRight) {if (postorder.size() 0) …...

Log4j Log4j2

前言 今天抽时间来把这个日志框架学学&#xff0c;毕竟经常用&#xff0c;虽然不用自己写&#xff0c;但是书到用时方恨少&#xff0c;技多不压身。而且最近我的 GUI 软件中有一个关于日志问题的希望学完能够感觉解决掉。 Log4j & Log4j2 Log4j2 是 Log4j 的升级版&#x…...

C语言——如何进行文件操作

大家好&#xff0c;我是残念&#xff0c;希望在你看完之后&#xff0c;能对你有所帮助&#xff0c;有什么不足请指正&#xff01;共同学习交流 本文由&#xff1a;残念ing原创CSDN首发&#xff0c;如需要转载请通知 个人主页&#xff1a;残念ing-CSDN博客&#xff0c;欢迎各位→…...

python中for循环的几个现象

1. 运行如下代码 l [{}, {}, {}] for k in l:k[1] 1 print(l) 输出为 [{1: 1}, {1: 1}, {1: 1}]2. 运行如下代码 l [{}, {}, {}] for k in l:k {1:1} print(l) 输出为 [{}, {}, {}] 3. 运行如下代码 l [1,2,3] for k in l:k k * 2 print(l)输出为 [1, 2, 3…...

openssl3.2 - 测试程序的学习 - 准备openssl测试专用工程的模板

文章目录 openssl3.2 - 测试程序的学习 - 准备openssl测试专用工程的模板概述笔记工程中需要的openssl的库实现补充 - 最终的模板工程END openssl3.2 - 测试程序的学习 - 准备openssl测试专用工程的模板 概述 openssl3.2 - 测试程序的学习 整了几个test.c, 每开一个新的测试工…...

Delphi.cz采访​Embarcadero​捷克共和国办事处经理:理查德·库巴特 - 第一部分

Embarcadero捷克办事处主任理查德库巴特&#xff08;Richard Kubt&#xff0c;55 岁&#xff09;接受了我的采访。 Radek Červinka (RČ)&#xff1a;库巴特先生您好&#xff0c;感谢您抽出时间访问 delphi.cz。 一开始&#xff1a;我在某处听说您是一名程序员&#xff0c;从…...

AI投资或成科技裁员罪魁祸首

最近的科技裁员让许多人对这个行业的稳定性产生了疑问。然而&#xff0c;仔细观察发现&#xff0c;这些裁员并不是经济困境的迹象&#xff0c;而是科技公司为了重新调整优先事项并投资未来而进行的战略举措。科技行业正投入数十亿美元用于人工智能&#xff08;AI&#xff09;&a…...

解读BEVFormer,新一代自动驾驶视觉工作的基石

文章出处 BEVFormer这篇文章很有划时代的意义&#xff0c;改变了许多视觉领域工作的pipeline[2203.17270] BEVFormer: Learning Birds-Eye-View Representation from Multi-Camera Images via Spatiotemporal Transformers (arxiv.org)https://arxiv.org/abs/2203.17270 BEV …...

【React教程】(1) React简介、React核心概念、React初始化

目录 ReactReact 介绍React 特点React 的发展历史React 与 Vue 的对比技术层面开发团队社区Native APP 开发 相关资源链接 EcmaScript 6 补充React 核心概念组件化虚拟 DOM 起步初始化及安装依赖Hello World React React 介绍 React 是一个用于构建用户界面的渐进式 JavaScrip…...

云计算中的弹性是什么?

云弹性是指当客户需求增加或减少时&#xff0c;自动从数据中心配置和取消配置资源。这使得云资源(包括计算、存储和内存资源)能够根据需求变化快速重新分配。CPU/处理、内存、输入/输出带宽和存储容量等计算资源可以根据需要增加或减少&#xff0c;而不会影响系统性能。 它旨在…...

Vue3基础:pnpm是什么?npm和pnpm的区别?如何使用pnpm?

pnpm 是一个流行的 JavaScript 包管理器&#xff0c;类似于 npm 和 yarn。它是 performant npm 的缩写&#xff0c;意在表明它是一个更高效的 npm 替代品。pnpm 的主要特点和优势包括&#xff1a; 高效的存储空间使用 pnpm 使用称为“内容寻址存储”的机制来存储 npm 包。这意…...

vue中父组件直接调用子组件方法(通过ref)

目录 1、vue2 中&#xff0c;父组件调用子组件的方法 2、vue3 中&#xff0c;父组件调用子组件的方法 1、vue2 中&#xff0c;父组件调用子组件的方法 在Vue 2中&#xff0c;父组件可以通过使用ref属性来引用子组件的实例&#xff0c;然后通过该实例调用子组件的方法。 首先…...

Gunicorn性能优化:提升Python Web应用的服务效率

在Python Web开发中&#xff0c;Gunicorn作为WSGI HTTP服务器&#xff0c;常常作为Web应用&#xff08;如Django或Flask&#xff09;与反向代理或负载均衡器之间的桥梁。为了充分发挥其性能&#xff0c;本文将提供一些实用的Gunicorn配置建议。 Gunicorn架构 Gunicorn采用了预…...

如何使用ssh key免密码登录服务器?

以下是使用密钥对免密码登录服务器的具体指令操作步骤&#xff1a; 步骤一&#xff1a;生成密钥对 在本地电脑上打开终端或命令提示符&#xff0c;运行以下命令生成密钥对&#xff1a; ssh-keygen -t rsa -C "your_emailexample.com" 该命令会提示您选择保存密钥…...

macos Android平台签名证书(.keystore)

一、申请appid的使用说明&#xff08;有appid的请忽略申请appid&#xff09; 创建应用 申请的appid在源码视图填写后会自动生成一个对应的包名 ⚠️注意&#xff1a;申请appid的时候应用名称和项目名称保持一致。 二、 Android如何使用自用证书进行打包 1.找到安装jdk的路径…...

Kotlin快速入门系列2

Kotlin的基本数据类型 Kotlin 的基本数值类型包括 Byte、Short、Int、Long、Float、Double 等。不同于 Java 的是&#xff0c;字符不属于数值类型&#xff0c;是一个独立的数据类型。 Java和kotlin数据类型对照如下&#xff1a; Java基本数据类型 Kotlin对象数据类型 数据类…...

单片机之keil软件环境搭建

简介 Keil提供了包括C编译器、宏汇编、链接器、库管理和一个功能强大的仿真调试器等在内的完整开发方案&#xff0c;通过一个集成开发环境&#xff08;μVision&#xff09;将这些部分组合在一起。     目前软件对中文的支持不友好&#xff0c;不建议安装网上的一些汉化包…...

数学公式OCR识别php 对接mathpix api 使用公式编译器

数学公式OCR识别php 对接mathpix api 一、注册账号官网网址&#xff1a;https://mathpix.com 二、该产品支持多端使用注意说明&#xff08;每月10次&#xff09; 三、api 对接第一步创建create keyphp对接api这里先封装两个请求函数&#xff0c;get 和post &#xff0c;通过官方…...

MySQL原理(二)存储引擎(1)概述

一、存储引擎介绍 1、概念&#xff1a; &#xff08;1&#xff09;MySQL中的数据用各种不下同的技术存储在文件中&#xff0c;每一种技术都使用不同的存储机制、索引技巧、锁定水平并最终提供不同的功能和能力&#xff0c;这些不同的技术以及配套的功能在MySQL中称为存储引擎…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...