【代码随想录二刷】Day18-二叉树-C++
代码随想录二刷Day18
今日任务
513.找树左下角的值
112.路径总和
113.路径总和ii
106.从中序与后序遍历序列构造二叉树
105.从前序与中序遍历序列构造二叉树
语言:C++
513.找树左下角的值
链接:https://leetcode.cn/problems/find-bottom-left-tree-value/
递归
class Solution {
public:int maxDepth = INT_MIN; //这里要用负数,避免树只有一层结构时无法更新resint res = 0;void traversal(TreeNode* root, int depth){if(root == NULL) return;if(root->left == NULL && root->right == NULL){if(depth > maxDepth){ //保证是最左边的元素,如果是同一层元素的话,不会更新maxDepth和res的值maxDepth = depth;res = root->val;}return;}if(root->left){traversal(root->left, depth + 1);}if(root->right){traversal(root->right, depth + 1);}}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return res;}
};
迭代
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;que.push(root);int res = 0;while(!que.empty()){int n = que.size();for(int i = 0; i < n; i++){TreeNode* cur = que.front();que.pop();if(i == 0){res = cur->val;}if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}}return res;}
};
112.路径总和
链接:https://leetcode.cn/problems/path-sum/
递归
class Solution {
public:int curSum = 0;bool traversal(TreeNode* root, int target){if(root == NULL) return false;if(root->left == NULL && root->right == NULL && target != root->val) return false;if(root->left == NULL && root->right == NULL && target == root->val) return true;bool left = traversal(root->left, target - root->val);bool right = traversal(root->right, target - root->val);return left || right;}bool hasPathSum(TreeNode* root, int targetSum) {if(root == NULL) return false;return traversal(root, targetSum);}
};
迭代
class Solution {
public:int curSum = 0;bool traversal(TreeNode* root, int targetSum){stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* cur = st.top();if(cur != NULL){st.push(NULL);curSum += cur->val; //中if(cur->left == NULL && cur->right == NULL && curSum == targetSum) return true;if(cur->right) st.push(cur->right); //右if(cur->left) st.push(cur->left); //左}else{st.pop(); //NULLcur = st.top();st.pop();curSum -= cur->val;}}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root == NULL) return false;return traversal(root, targetSum);}
};
113.路径总和ii
链接:https://leetcode.cn/problems/path-sum-ii/
递归
class Solution {
public:vector<vector<int>> res;vector<int> path;void traversal(TreeNode* root, int target){if(root == NULL) return;if(root->left == NULL && root->right == NULL && target != root->val) return;if(root->left == NULL && root->right == NULL && target == root->val){path.push_back(root->val);res.push_back(path);path.pop_back(); //回溯return;}if(root->left){path.push_back(root->val);traversal(root->left, target - root->val);path.pop_back();}if(root->right){path.push_back(root->val);traversal(root->right, target - root->val);path.pop_back();}}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if(root == NULL) return res;traversal(root, targetSum);return res;}
};
迭代
class Solution {
public:vector<vector<int>> res;vector<int> path;int curSum = 0;vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if(root == NULL) return res;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* cur = st.top();if(cur != NULL){st.push(NULL);curSum += cur->val;path.push_back(cur->val);if(cur->left == NULL && cur->right == NULL && curSum == targetSum){res.push_back(path);}if(cur->right) st.push(cur->right);if(cur->left) st.push(cur->left);}else{st.pop();cur = st.top();st.pop();curSum -= cur->val;path.pop_back();}}return res;}
};
106.从中序与后序遍历序列构造二叉树
链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
递归
class Solution {
public:TreeNode* traversal(vector<int>& inorder, vector<int>& postorder){if(postorder.size() == 0) return NULL;int val = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(val);if(postorder.size() == 1) return root;int i;for(i = 0; i < inorder.size(); i++){if(inorder[i] == val) break;}postorder.resize(postorder.size() - 1);vector<int> left_in(inorder.begin(), inorder.begin() + i);vector<int> left_post(postorder.begin(), postorder.begin() + i);root->left = traversal(left_in, left_post);vector<int> right_in(inorder.begin() + i + 1, inorder.end());vector<int> right_post(postorder.begin() + i, postorder.end());root->right = traversal(right_in, right_post);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {return traversal(inorder, postorder);}
};
105.从前序与中序遍历序列构造二叉树
链接:https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
递归
class Solution {
public:TreeNode* traversal(vector<int>& preorder, vector<int>& inorder){if(inorder.size() == 0) return NULL;int val = preorder[0];TreeNode* root = new TreeNode(val);if(inorder.size() == 1) return root;int i;for(i = 0; i < inorder.size(); i++){if(inorder[i] == val) break;}vector<int> left_pre(preorder.begin() + 1, preorder.begin() + 1 + i);vector<int> left_in(inorder.begin(), inorder.begin() + i);root->left = traversal(left_pre, left_in);vector<int> right_pre(preorder.begin() + 1 + i, preorder.end());vector<int> right_in(inorder.begin() + i + 1, inorder.end());root->right = traversal(right_pre, right_in);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return traversal(preorder, inorder);}
};
相关文章:
【代码随想录二刷】Day18-二叉树-C++
代码随想录二刷Day18 今日任务 513.找树左下角的值 112.路径总和 113.路径总和ii 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树 语言:C 513.找树左下角的值 链接:https://leetcode.cn/problems/find-bottom-left-tree-va…...
制造业的云ERP在外网怎么访问?内网服务器一步映射到公网
随着企业信息化、智能化时代的到来,很多制造业企业都在用云ERP。用友U 9cloud通过双版本公有云专属、私有云订阅、传统软件购买三种模式满足众多制造业企业的需求,成为一款适配中型及中大型制造业的云ERP,是企业数智制造的创新平台。 用友U 9…...
zookeeper 复习 ---- 练习
zookeeper 复习 ---- 练习在同一节点配置三个 zookeeper,配置正确的是? A: zoo1.cfg tickTime2000 initLimit5 syncLimit2 dataDir/var/lib/zookeeper/zoo1 clientPort2181 server.1localhost:2666:3666 server.2localhost:2667:3667 serv…...
2023年全国最新道路运输从业人员精选真题及答案1
百分百题库提供道路运输安全员考试试题、道路运输从业人员考试预测题、道路安全员考试真题、道路运输从业人员证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 11.在以下选项中关于安全生产管理方针描述正确的是(…...
Java每日一练——Java简介与基础练习
系列文章目录 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 例如:第一章 Python 机器学习入门之pandas的使用 文章目录 目录 系列文章目录 文章目录 前言 一、简述解释型语言与编译型语言 二、Java语言的执行流程 2.1、…...
解决Edge浏览器主页被篡改问题,或许可以帮你彻底解决
问题描述: 之前从一个第三方网站下载了一个不知名软件,接着电脑就各种下载360全家桶之类的软件,后来问题解决了,但是还残留了一些问题,前几天发现edge浏览器的主页被改成了360导航,就是那个该死的hao123&a…...
字符设备驱动基础(一)
目录 一、Linux内核对设备的分类 linux的文件种类: Linux内核按驱动程序实现模型框架的不同,将设备分为三类: 总体框架图: 二、设备号------内核中同类设备的区分 三、申请和注销设备号 四、函数指针复习 4.1、 内存四区 …...
将 Supabase 作为下一个后端服务
对于想快速实现一个产品而言,如果使用传统开发,又要兼顾前端开发,同时又要花费时间构建后端服务。然而有这么一个平台(Baas Backend as a service)后端即服务,能够让开发人员可以专注于前端开发,…...
14:高级篇 - CTK 服务工厂 简述
作者: 一去、二三里 个人微信号: iwaleon 微信公众号: 高效程序员 一般情况下,服务对象在被注册之后,任何其它的 Plugin 在请求该服务时,CTK Plugin Framework 都返回的是同一个对象。倘若要为每一个 Plugin 消费者返回不同的服务对象,或者在真正需要该服务对象时才创建…...
Java中的链表实现介绍
Java中的链表实现介绍 学习数据结构的的链表和树时,会遇到节点(node)和链表(linked list)这两个术语,节点是处理数据结构的链表和树的基础。节点是一种数据元素,包括两个部分:一个是…...
演示Ansible中的角色使用方法(ansible roles)
文章目录一、ansible 角色简介二、roles目录结构三、role存放的路径:配置文件ansible.cfg中定义四、创建目录结构五、playbook中使用rolesplaybook变量会覆盖roles中的定义变量六、控制任务执行顺序七、ansible—galaxy命令工具八、安装选择的角色1.从网上下载&…...
Bash Shell 通过ls命令筛选文件
Bash Shell 通过ls命令及其管道根据大小名称筛选文件 最近参与的项目当中有需要用pyarmor加密项目的要求,听网上吹的pyarmor都那么神,用了一下感觉也一般,试用版普通模式下文件加密居然还有大小32KB的限制,加密到一半就失败了&am…...
2023-2-18 刷题情况
删列造序 III 题目描述 给定由 n 个小写字母字符串组成的数组 strs ,其中每个字符串长度相等。 选取一个删除索引序列,对于 strs 中的每个字符串,删除对应每个索引处的字符。 比如,有 strs [“abcdef”,“uvwxyz”] …...
【Linux】进程控制
文章目录进程创建简单认识一下fork()函数为什么fork()会有两个返回值fork通过写时拷贝的方式创建子进程进程终止进程退出码进程退出的方式exit()和_exit()进程等待进程等待方法 -- wait()和waitpid()status参数解释waitpid()的pid参数waitpid()的options参数 - 阻塞和非阻塞进程…...
谷歌seo快排技术怎么做?Google排名霸屏推广原理
本文主要分享关于谷歌快速排名的方法和所需要的条件。 本文由光算创作,有可能会被剽窃和修改,我们佛系对待这种行为吧。 首先提出一个问题:谷歌seo快排技术怎么做?如何达到谷歌霸屏的效果? 答案是:利用谷…...
MySQL的优化
目录 一.概念 二.查看SQL执行频率 三.定位低效率执行SQL 定位低效率执行SQL—慢查询日志 操作 定位低效率执行SQL—show processlist 四.explain分析执行计划 字段说明 explain中的id explain中的select_type explain中的type explain中的table explain中的rows ex…...
实现qq群消息接收和发送功能
QQWebsocketClient是什么 实现qq群消息接收和发送功能,基于websocket技术和cqhttp服务开发 一、 效果截图 二、实现思路 使用cqhttp进行socket反向代理,获取qq聊天的所有消息 编写java客户端,连接至cqhttp服务器获取聊天消息 获取聊天消…...
压缩20M文件从30秒到1秒的优化过程
压缩20M文件从30秒到1秒的优化过程 有一个需求需要将前端传过来的10张照片,然后后端进行处理以后压缩成一个压缩包通过网络流传输出去。之前没有接触过用Java压缩文件的,所以就直接上网找了一个例子改了一下用了,改完以后也能使用࿰…...
如何选择合适的固态继电器?
如何选择合适的固态继电器? 在选择固态继电器(SSR)时,应根据实际应用条件和SSR性能参数,特别要考虑到使用中的过流和过压条件以及SSR的负载能力,这有助于实现固态继电器的长寿命和高可靠性。然后࿰…...
SAP 忘记SAP系统Client 000的所有账号密码
忘记SAP系统Client 000的所有账号密码。 Solution 在SAP系统DB中删除账号SAP*,SAP系统会自动创建SAP*这个账号,然后初始密码是“PASS”,这样就获得Client 000 SAP*账号。 Step by Step 以Oracle数据库为例: 1.以<SID>ADM账…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
