代码随想录算法训练营day21 | 513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树
513.找树左下角的值
迭代法比较简单,层序遍历,找到最下面一层的第一个节点。题目已经说明节点数>=1了
class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:queue = collections.deque()queue.append(root)result = root.valwhile queue:size = len(queue)for i in range(size):node = queue.popleft()if i == 0:result = node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)return result
递归法
题解中遇到叶子节点并且当前深度比最大深度更大时更换结果值,但是最深的节点必定是叶子节点,所以不必判断是叶子节点
class Solution:def __init__(self):self.result = 0self.max_depth = 0def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:self.getValue(root, 1)return self.resultdef getValue(self, node, depth):if not node:returnif depth > self.max_depth:self.max_depth = depthself.result = node.valself.getValue(node.left, depth+1)self.getValue(node.right, depth+1)
112. 路径总和
class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if not root:return Falsereturn self.traversal(root, 0, targetSum)def traversal(self, node, cur_sum, target_sum):if not node:return Falsecur_sum += node.valif not node.left and not node.right:if cur_sum == target_sum:return Truereturn self.traversal(node.left, cur_sum, target_sum) or self.traversal(node.right, cur_sum, target_sum)下面的代码思路更清晰
不要去累加然后判断是否等于目标和,那么代码比较麻烦,可以用递减,让计数器count初始为目标和,然后每次减去遍历路径节点上的数值。
class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if not root:return Falsereturn self.traversal(root, targetSum-root.val)def traversal(self, node, count):if not node.left and not node.right:return count == 0if node.left:if self.traversal(node.left, count-node.left.val):return Trueif node.right:if self.traversal(node.right, count-node.right.val):return Truereturn False
路径总和:返回是否存在路径
路径总和II:返回满足条件的所有路径
下面为路径总和II的代码
class Solution:def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:result = []if not root:return resultself.getPath(root, [root.val], result, targetSum-root.val)return resultdef getPath(self, node, path, result, count):if not node.left and not node.right:if count == 0:result.append(path[:])if node.left:path.append(node.left.val)self.getPath(node.left, path, result, count-node.left.val)path.pop()if node.right:path.append(node.right.val)self.getPath(node.right, path, result, count-node.right.val)path.pop()
106.从中序与后序遍历序列构造二叉树
下面为每层递归定义了新的vector(就是数组),既耗时又耗空间。可以使用索引的方式,每次确定区间的左右索引
class Solution:def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:if len(inorder) <= 0:returnvalue = postorder[-1]index = inorder.index(value)left = self.buildTree(inorder[0:index], postorder[0:index])right = self.buildTree(inorder[index+1:], postorder[index:-1])return TreeNode(value, left, right)
105. 从前序与中序遍历序列构造二叉树
class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:if not preorder:returnvalue = preorder[0]index = inorder.index(value)left = self.buildTree(preorder[1:index+1], inorder[0:index])right = self.buildTree(preorder[index+1:], inorder[index+1:])return TreeNode(value, left, right)
相关文章:
代码随想录算法训练营day21 | 513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树
513.找树左下角的值 迭代法比较简单,层序遍历,找到最下面一层的第一个节点。题目已经说明节点数>1了 class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:queue collections.deque()queue.append(root)result ro…...
微信小程序知识点归纳(一)
前言:适用于有一定基础的前端开发同学,完成从网页开发到小程序开发的知识转换。 先立框架,后砌墙壁 回顾:了解微信小程序开发流程-CSDN博客 初始页面结构,三部分pages、utils、配置,分别存放页面、工具类…...
wangEditor富文本编辑器与layui图片上传
记录:js 显示默认的wangEditor富文本编辑器内容和图片 <style>body {background-color: #ffffff;}.layui-form-select dl{z-index:100000;} </style> <div class"layui-form layuimini-form"><div class"layui-form-item"…...
爬虫学习:XPath提取网页数据
目录 一、安装XPath 二、XPath的基础语法 1.选取节点 三、使用XPath匹配数据 1.浏览器审查元素 2.具体实例 四、总结 一、安装XPath 控制台输入指令:pip install lxml 二、XPath的基础语法 XPath是一种在XML文档中查找信息的语言,可以使用它在HTM…...
【雅思写作】Vince9120雅思小作文笔记——P1 Intro(前言)
文章目录 链接P1 Intro(前言)字数限制题型综述(problem types overview)1. **柱状图(Bar Chart)** - 描述不同类别在某个或多个变量上的数据量比较。2. **线图(Line Graph)** - 展示…...
【面试干货】HTTPS 工作原理
【面试干货】HTTPS 工作原理 1、握手阶段(Handshake)2、密钥协商阶段3、加密通信阶段4、结束通信阶段 💖The Begin💖点点关注,收藏不迷路💖 HTTPS(HyperText Transfer Protocol Secureÿ…...
Cocos Creator 中编码规范 (6)
Cocos中命名规范 创建文件夹,全小写。创建脚本,首字母大写的驼峰形式。创建变量,首字母小写的驼峰形式 官方的编码规范...
Vue3:menu导航栏出现多个同一跳转路径的菜单处理
文章目录 需求整理实现思路实现过程 需求整理,实现思路 最近公司想将之前老的项目整理出来,因为这个老项目内容太杂什么页面都往里面塞,导致菜单特别多,公司就像将这个老的项目迁出来,这个旧的项目本来是后端PHP写的。…...
SAM轻量化应用Auto-SAM、Group-Mix SAM、RAP-SAM、STLM
1. Auto SAM(Auto-Prompting SAM for Mobile Friendly 3D Medical Image Segmentation) 1.1 面临问题 医学背景: (1)与自然图像相比,医学图像的尺寸更小,形状不规则,对比度更低。&…...
深度优化搜索DFS使用详解,看这篇就够了!!!
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树和图的算法。在最坏的情况下,深度优先搜索的性能为O(VE),其中V是顶点数,E是边数。DFS常用于解决连通性问题、路径问题、生成树问题等。 ### D…...
Apache SeaTunnel 正式发布2.3.5版本,功能增强及多个Bug修复
经过两个月的筹备,我们在2.3.4版本基础上进行了新一轮的迭代,本次更新不仅修复了多个关键问题,还引入了若干重要功能增强和性能优化。 在此,我们先提前感谢社区成员的贡献和支持,如果你想升级最新的版本,快…...
interview_bak
flink内存管理 JVM 存在的几个问题: Java 对象存储密度低。一个只包含 boolean 属性的对象占用了16个字节内存:对象头占了8个,boolean 属性占了1个,对齐填充占了7个。而实际上只需要一个bit(1/8字节)就够了。Full GC 会极大地影响性能,尤其是为了处理更大数据而开了很大…...
layui 数据表格 自动定位新增行位置
由于数据表格新增行后没有到新增到当前位置 继续增加的需求: 因为自己是新增行后到最后一行的 所以 就定位到最后一行 并且 高亮 高亮颜色浅 可自行更改 整理了一下 可根据 情况 修改 // 初始化滚动条位置变量 let tableScroll {scrollTob: 0,scrollLeft: 0,…...
window10下安装ubuntu系统以及docker使用
window10下安装ubuntu系统以及docker使用 1. 启用适用于Linux的Windwos子系统2.下载Linux内核更新包3.将 WSL 2 设置为默认版本4.安装Ubuntu<br />直接去Microsoft store里面直接搜索Ubuntu进行安装。5.可能出现的问题1.win10启动ubuntu报错 参考的对象类型不支持尝试的操…...
Netty核心组件介绍
Netty是一款用于创建高性能网络应用程序的高级框架。Netty的核心组件如下: Channel回调Future事件和ChannelHander Channel channel是Java NIO的一个基本构造。可以把Channel看作是传入或传出数据的载体。它可以被打开或关闭,连接或断开连接。 回调 …...
代码审计平台sonarqube的安装及使用
docker搭建代码审计平台sonarqube 一、代码审计关注的质量指标二、静态分析技术分类三、使用sonarqube的目的四、sonarqube流程五、docker快速搭建sonarqube六、sonarqube scanner的安装和使用七、sonarqube对maven项目进行分析八、sonarqube分析报告解析九、代码扫描规则定制十…...
C++ 使用nlohmann/json.hpp库读写json字符串
1. json库 我个人比较喜欢 nlohmann/json.hpp 这个库,因为它只需要一个hpp文件即可,足够轻量! 这是它的github地址。 2. 简单实例代码 #include <iostream> #include <json.hpp> #include <fstream> #include <stri…...
3GPP官网下载协议步骤
1.打开官网 https://www.3gpp.org/ 2.点击 3.在界面选择要找的series,跳转到查找界面 以V2X通信协议为例,论文中通常会看到许多应用: [7] “Study on evaluation methodology of new Vehicle-to-Everything (V2X) use cases for LTE and NR…...
【JAVA】Git 的基本概念和使用方式
Git是一个开源的分布式版本控制系统,由Linus Torvalds创建,用于有效、高速地处理从小到大的项目版本管理。以下是Git的一些基本概念和使用方式的深入探讨: 基本概念 1. 仓库(Repository) 仓库是Git用来保存你的项目…...
C++多态实现原理详解
阅读引言: 我想象了一下, 假如人有突然问我什么是多态, 我该如何给别人说清楚呢?所以写下这篇文章, 希望大家看完有所收获。 ①. 开胃小菜 先看这样一个开胃小菜 这里我有点小小的疑惑, 大小为啥是1。 在C…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
在 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…...
elementUI点击浏览table所选行数据查看文档
项目场景: table按照要求特定的数据变成按钮可以点击 解决方案: <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...
