代码随想录算法训练营| 找树左下角的值 、 路径总和 、 从中序与后序遍历序列构造二叉树
找树左下角的值
题目
参考文章
思路:这里寻找最左下角的值,其实用前中后序都是可以的,只要保证第一遍历的是左边开始就可以。设置Deep记录遍历的最大深度,deep记录当前深度。当遇到叶子节点时而且当前深度比最大深度还大则更换最大深度为deep并存储当前节点的值(这个时候说明遇到的就是当前深度下最左边的叶子节点,但不一定是最最大深度的最左边的叶子节点,还要继续往后遍历)。最后value存储的结果,就是最大深度下最左下角的值了
代码:
class Solution {private int Deep = -1;private int value = 0;public int findBottomLeftValue(TreeNode root) {value = root.val;findLeftValue(root,0);return value;}private void findLeftValue (TreeNode root,int deep) {if (root == null) return;if (root.left == null && root.right == null) {if (deep > Deep) {value = root.val;Deep = deep;}}if (root.left != null) findLeftValue(root.left,deep + 1);if (root.right != null) findLeftValue(root.right,deep + 1);}
}
路径总和
题目1
题目2
参考文章
思路1:其实这里的用前中后序都是可以的,重要的是回溯的过程。每次遍历节点,就把target值减去当前节点值,然后判断是否为叶子节点,如果是叶子节点就直接返回true,因为题目意思就是遇到一条路径等于target值就直接返回即可。当不是叶子节点且节点不为空,就继续遍历节点值,直到遇到一条路径等于target就一直返回true到根节点,否则就是返回false
代码1:
class Solution {public boolean hasPathSum(TreeNode root, int targetSum) {if (root == null) {return false;}targetSum -= root.val;// 叶子结点if (root.left == null && root.right == null) {return targetSum == 0;}if (root.left != null) {boolean left = hasPathSum(root.left, targetSum);if (left) { return true;}}if (root.right != null) {boolean right = hasPathSum(root.right, targetSum);if (right) { return true;}}return false;}
}
思路2:
这题和题目1其实思路一样,只是不是直接返回true,而是把这条路径的值全部存起来,最后把所有等于target值的路径输出
代码2:
class Solution {public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> res = new ArrayList<>();if (root == null) return res; List<Integer> path = new LinkedList<>();preorderdfs(root, targetSum, res, path);return res;}public void preorderdfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {path.add(root.val);// 遇到了叶子节点if (root.left == null && root.right == null) {// 找到了和为 targetsum 的路径if (targetsum - root.val == 0) {res.add(new ArrayList<>(path));}return; // 如果和不为 targetsum,返回}if (root.left != null) {preorderdfs(root.left, targetsum - root.val, res, path);path.remove(path.size() - 1); // 回溯}if (root.right != null) {preorderdfs(root.right, targetsum - root.val, res, path);path.remove(path.size() - 1); // 回溯}}
}
从中序与后序遍历序列构造二叉树
题目
参考文章
思路:其实这道题就是理解二叉树的一个过程,构建二叉树,首先得知道前序中序或中序后序,知道前序后序是不能构造二叉树的。以后序中序为例;这里重要的是找到根节点以及找到根节点后如何分割这个后序中序数组。后序数组中,最后一个元素就是根节点,然后通过这个根节点的值,找到在对应中序的下标(index);找到下标之后,就是分割后序中序数组,通过index找到左中序右中序,以及左后序和右后序,重点注意右中序,因为涉及数组溢出和超出数组范围的情况(主要是因为在中序数组中间会出现要构建子树的情况);得到分割后的数组,就继续调用构建树的方法即可
代码:
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if(postorder.length == 0 || inorder.length == 0)return null;return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);}private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd){if(postorderStart == postorderEnd)return null;int rootVal = postorder[postorderEnd - 1];TreeNode root = new TreeNode(rootVal);int middleIndex;for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++){if(inorder[middleIndex] == rootVal)break;}int leftInorderStart = inorderStart; int leftInorderEnd = middleIndex;int rightInorderStart = middleIndex + 1;int rightInorderEnd = inorderEnd;int leftPostorderStart = postorderStart;int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);//这个是为了防止数组溢出,因为有可能中序数组中间部分是要构建树的,所以postorderStart和inorderStart可能不为零的情况,所以要减去int rightPostorderStart = leftPostorderEnd;int rightPostorderEnd = postorderEnd - 1;root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostorderStart, leftPostorderEnd);root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostorderStart, rightPostorderEnd);return root;}
}
相关文章:
代码随想录算法训练营| 找树左下角的值 、 路径总和 、 从中序与后序遍历序列构造二叉树
找树左下角的值 题目 参考文章 思路:这里寻找最左下角的值,其实用前中后序都是可以的,只要保证第一遍历的是左边开始就可以。设置Deep记录遍历的最大深度,deep记录当前深度。当遇到叶子节点时而且当前深度比最大深度还大则更换最…...
【开源免费】基于SpringBoot+Vue.JS服装销售平台(JAVA毕业设计)
博主说明:本文项目编号 T 054 ,文末自助获取源码 \color{red}{T054,文末自助获取源码} T054,文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析…...
人工智能与自然语言处理发展史
前言 在科技的浪潮中,人工智能 (AI) 作为一股不可阻挡的力量,持续推动着社会与科技的进步。本博客旨在深入剖析人工智能及其核心领域——神经网络、自然语言处理、统计语言模型、以及大规模语言模型——的演进历程,以专业的视角展现这一领域…...
0基础跟德姆(dom)一起学AI 机器学习01-机器学习概述
【知道】人工智能 - Artificial Intelligence 人工智能 - AI is the field that studies the synthesis and analysis of computational agents that act intelligently - AI is to use computers to analog and instead of human brain - 释义 - 仿智; 像人…...
yakit使用教程(一,下载并进行基础配置)
一,yakit简介 YAKIT(Yet Another Knife for IT Security)是一款网络安全单兵工具,专为个人渗透测试员和安全研究人员设计。它整合了一系列实用的安全工具,例如密码破解工具、网络扫描器、漏洞利用工具等,帮…...
计算机毕业设计电影票购买网站 在线选票选座 场次订票统计 新闻留言搜索/springboot/javaWEB/J2EE/MYSQL数据库/vue前后分离小程序
系统功能 在线选票选座:用户可浏览电影场次,选择座位并生成订单。场次订票统计:系统实时统计各场次订票情况,便于影院管理。新闻发布与留言:发布最新电影资讯,用户可留言互动。搜索功能&a…...
DES、3DES 算法及其应用与安全性分析
一、引言 1.1 研究背景 在当今数字化时代,信息安全至关重要。对称加密算法作为信息安全领域的重要组成部分,发挥着关键作用。DES(Data Encryption Standard)作为早期的对称加密算法,由美国国家标准局于 1977 年采纳为数据加密标准。随着计算机运算能力的不断增强,DES 算…...
TypeScript介绍和安装
TypeScript介绍 TypeScript是由微软开发的一种编程语言,它在JavaScript的基础上增加了静态类型检查。静态类型允许开发者在编写代码时指定变量和函数的类型,这样可以在编译时捕获潜在的错误,而不是等到运行时才发现问题。比如,你…...
NetworkPolicy访问控制
NetworkPolicy是Kubernetes中一种用于控制Pod之间以及Pod与外部网络之间流量的资源对象。它可以帮助你在 IP 地址或端口层面(OSI 第 3 层或第 4 层)控制网络流量。NetworkPolicy 资源使用标签选择 Pod,并定义选定 Pod 所允许的通信规则。它可…...
C++面向对象基础
目录 一.作用域限定符 1.名字空间 2.类内声明,类外定义 二.this指针 1 概念 2.功能 2.1 类内调用成员 2.2 区分重名的成员变量和局部变量 2.3链式调用 三.stastic关键字 1.静态局部变量 2 静态成员变量 3 静态成员函数 4 单例设计模式(了解…...
遥感图像变换检测实践上手(TensorRT+UNet)
目录 简介 分析PyTorch示例 onnx模型转engine 编写TensorRT推理代码 main.cpp测试代码 小结 简介 这里通过TensorRTUNet,在Linux下实现对遥感图像的变化检测,示例如下: 可以先拉去代码:RemoteChangeDetection 分析PyTorch示…...
Transformers 引擎,vLLM 引擎,Llama.cpp 引擎,SGLang 引擎,MLX 引擎
1. Transformers 引擎 开发者:Hugging Face主要功能:Transformers 库提供了对多种预训练语言模型的支持,包括 BERT、GPT、T5 等。用户可以轻松加载模型进行微调或推理。特性: 多任务支持:支持文本生成、文本分类、问答…...
牛顿迭代法求解x 的平方根
牛顿迭代法是一种可以用来快速求解函数零点的方法。 为了叙述方便,我们用 C C C表示待求出平方根的那个整数。显然, C C C的平方根就是函数 f ( x ) x c − C f(x)x^c-C f(x)xc−C 的零点。 牛顿迭代法的本质是借助泰勒级数,从初始值开始快…...
端口隔离配置的实验
端口隔离配置是一种网络安全技术,用于在网络设备中实现不同端口之间的流量隔离和控制。以下是对端口隔离配置的详细解析: 基本概念:端口隔离技术允许用户将不同的端口加入到隔离组中,从而实现这些端口之间的二层数据隔离。这种技…...
洛谷 P10456 The Pilots Brothers‘ refrigerator
[Problem Discription] \color{blue}{\texttt{[Problem Discription]}} [Problem Discription] 给定一个 4 4 4 \times 4 44 的网格,每个网格有 0 , 1 0,1 0,1 两种状态。求最少可以通过多少次操作使得整个网格全部变成 1 1 1。 每次操作你需要选定一个格点 …...
windows+vscode+arm-gcc+openocd+daplink开发arm单片机程序
windowsvscodearm-gccopenocddaplink开发arm单片机程序,脱离keil。目前发现的最佳解决方案是,使用vscodeembedded ide插件。 Embedded IDE官方教程文档...
Mysql梳理10——使用SQL99实现7中JOIN操作
10 使用SQL99实现7中JOIN操作 10.1 使用SQL99实现7中JOIN操作 本案例的数据库文件分享: 通过百度网盘分享的文件:atguigudb.sql 链接:https://pan.baidu.com/s/1iEAJIl0ne3Y07kHd8diMag?pwd2233 提取码:2233 # 正中图 SEL…...
24.9.27学习笔记
Xavier初始化,也称为Glorot初始化,是一种在训练深度神经网络时用于初始化网络权重的策略。它的核心思想是在网络的每一层保持前向传播和反向传播时的激活值和梯度的方差尽可能一致,以避免梯度消失或梯度爆炸的问题。这种方法特别适用于激活函…...
C++第3课——保留小数点、比较运算符、逻辑运算符、布尔类型以及if-else分支语句(含视频讲解)
文章目录 1、课程笔记2、课程视频 1、课程笔记 #include<iostream>//头文件 input output #include<cmath> //sqrt()所需的头文件 #include<iomanip>//setprecision(1)保留小数点位数所需的头文件 using namespace std; int main(){/*复习上节课内容1、…...
韩媒专访CertiK首席商务官:持续关注韩国市场,致力于解决Web3安全及合规问题
作为Web3.0头部安全公司,CertiK在KBW期间联合CertiK Ventures举办的活动引起了业界的广泛关注。CertiK一直以来与韩国地方政府保持着紧密合作关系,在合规领域提供强有力的支持。而近期重磅升级的CertiK Ventures可以更好地支持韩国本地的区块链项目。上述…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
