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

python coding with ChatGPT 打卡第17天| 二叉树:找树左下角的值、路径总和

相关推荐
python coding with ChatGPT 打卡第12天| 二叉树:理论基础
python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历
python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历
python coding with ChatGPT 打卡第15天| 二叉树:翻转二叉树、对称二叉树
python coding with ChatGPT 打卡第16天| 二叉树:完全二叉树、平衡二叉树、二叉树的所有路径、左叶子之和

文章目录

  • 找树左下角的值
    • Key Points
    • 相关题目
    • 视频讲解
    • 重点分析
  • 路径总和
    • Key Points
    • 相关题目
    • 视频讲解
    • 重点分析

找树左下角的值

Key Points

找出树的最后一行的最左边的值

相关题目

513. 找树左下角的值

视频讲解

递归中带着回溯

重点分析

方法一:层序遍历

def findBottomLeftValue(root):queue_record = [root]res = root.valwhile queue_record:level_size = len(queue_record)for i in range(level_size):node = queue_record.pop(0)if i==0:res = node.valif node.left:queue_record.append(node.left)if node.right:queue_record.append(node.right)return res

方法二:层序遍历简洁版

class Solution(object):def findBottomLeftValue(self, root):if not root:return Nonequeue = [root]while queue:current = queue.pop(0)# 先右后左加入队列,确保左边的节点最后被处理,从而保留在current中if current.right:queue.append(current.right)if current.left:queue.append(current.left)# 循环结束时,current中存储的是最后一层最左边的节点return current.val

这段代码使用了BFS来确保按层遍历树的节点,并且通过在每层遍历时记录遍历到的第一个节点值,最终找到了最后一行最左边的值。请注意,这里故意先将右子节点加入队列,然后加入左子节点,是为了在处理每一层的节点时,最后处理左子节点,但是对于寻找最后一行最左边的值的目的而言,只需要记录每一层第一次访问的节点即可,因此实际上你可以按照正常的顺序(先左后右)加入队列,然后最后处理的节点即为所求。这样的处理方式更直观且易于理解。

方法三:递归法

class Solution:def findBottomLeftValue(self, root: TreeNode) -> int:self.max_depth = float('-inf')self.result = Noneself.traversal(root, 0)return self.resultdef traversal(self, node, depth):if not node.left and not node.right:if depth > self.max_depth:self.max_depth = depthself.result = node.valreturnif node.left:self.traversal(node.left, depth+1)if node.right:self.traversal(node.right, depth+1)

递归的另一种写法,由ChatGPT提供
在这里插入图片描述

路径总和

Key Points

叶子节点是指没有子节点的节点。

相关题目

112. 路径总和
113. 路径总和ii

视频讲解

路径总和

重点分析

112
方法一:递归

def hasPathSum(root: TreeNode, targetSum: int) -> bool:if not root:return False# 更新目标和targetSum -= root.val# 如果是叶子节点,检查目标和是否为0if not root.left and not root.right:return targetSum == 0# 递归遍历左右子节点return hasPathSum(root.left, targetSum) or hasPathSum(root.right, targetSum)

在这里插入图片描述方法二:迭代法

def hasPathSum(root, targetSum):if not root:return Falsestack_record = [(root, root.val)]while stack_record:node, value = stack_record.pop()if not node.left and not node.right:if value == targetSum:return Trueelse:if node.right:stack_record.append((node.right, value+node.right.val))if node.left:stack_record.append((node.left, value + node.left.val))return False

113 方法一:递归法
在这里插入图片描述

class Solution:def pathSum(self, root: TreeNode, targetSum: int) -> [[int]]:result = []self.dfs(root, targetSum, [], result)return resultdef dfs(self, node, targetSum, path, result):if not node:return# 添加当前节点到路径path.append(node.val)# 检查是否是叶子节点且路径总和等于目标和if not node.left and not node.right and sum(path) == targetSum:result.append(list(path))else:# 递归遍历左右子节点self.dfs(node.left, targetSum, path, result)self.dfs(node.right, targetSum, path, result)# 回溯前去除当前节点path.pop()# 示例使用
# 假设有一个二叉树和目标和,可以创建TreeNode实例并调用Solution().pathSum(root, targetSum)来获取结果

在这里插入图片描述

方法二:迭代法

def pathSum(root, targetSum):if not root:return []stack_record = [(root, [root.val])]res = []while stack_record:node, value_list = stack_record.pop()if not node.left and not node.right:if sum(value_list) == targetSum:res.append(value_list)else:if node.right:stack_record.append((node.right, value_list+[node.right.val]))if node.left:stack_record.append((node.left, value_list + [node.left.val]))return res

相关文章:

python coding with ChatGPT 打卡第17天| 二叉树:找树左下角的值、路径总和

相关推荐 python coding with ChatGPT 打卡第12天| 二叉树:理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树:翻转…...

2020年通信工程师初级 综合能力 真题

文章目录 第1章 通信职业道德,1-4第2章 法律法规,5-16第3章 计算机应用基础,第5章 现代通信网,38英语题,91 第1章 通信职业道德,1-4 1、职业道德在形式上具有()特点。 A.一致性 B.统一性 C.多样性 D.一般性…...

12.0 Zookeeper 数据同步流程

在 Zookeeper 中,主要依赖 ZAB 协议来实现分布式数据一致性。 ZAB 协议分为两部分: 消息广播崩溃恢复 消息广播 Zookeeper 使用单一的主进程 Leader 来接收和处理客户端所有事务请求,并采用 ZAB 协议的原子广播协议,将事务请求…...

作业2.6

一、填空题 1、一个类的头文件如下所示&#xff0c;num初始化值为5&#xff0c;程序产生对象T&#xff0c;且修改num为10&#xff0c;并使用show()函数输出num的值10。 #include <iostream.h> class Test { private: static int num; public: Test(int); void sh…...

Qt应用软件【协议篇】TCP示例

文章目录 TCP协议简介Qt中的TCP编程完整代码示例实际使用中的技巧实际使用中的注意事项TCP协议简介 TCP(传输控制协议)是一种面向连接的、可靠的、基于字节流的传输层通信协议。与UDP不同,TCP提供了数据包排序、重传机制、流量控制和拥塞控制,确保了数据传输的可靠性和顺序…...

C# CAD交互界面-自定义面板集(四)

运行环境 vs2022 c# cad2016 调试成功 一、引用 using Autodesk.AutoCAD.Runtime; using Autodesk.AutoCAD.Windows; using System.Windows.Forms; 二、程序说明 创建自定义面板集&#xff08;PaletteSet&#xff09;的C#命令方法实现。该方法名为CreatePalette&#xff…...

物流自动化移动机器人|HEGERLS三维智能四向穿梭车助力优化企业供应链

智能化仓库/仓储贯穿于物流的各个环节&#xff0c;不局限于存储、输送、分拣、搬运等单一作业环节的自动化&#xff0c;更多的是利用科技手段实现整个物流供应链流程的自动化与智能化&#xff0c;将传统自动化仓储物流各环节进行多维度的有效融合。 例如在数智化物流仓储的建设…...

EasyExcel下载带下拉框和批注模板

EasyExcel下载带下拉框和批注模板 一、 代码实现 controller下载入口 /***下载excel模板* author youlu* date 2023/8/14 17:31* param response* param request* return void*/PostMapping("/downloadTemplate")public void downloadExcel(HttpServletResponse r…...

C语言之字符逆序(牛客网)

个人主页&#xff08;找往期文章包括但不限于本期文章中不懂的知识点&#xff09;&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 字符逆序__牛客网 题目&#xff1a; 思路&#xff1a;既然有空格就不能用scanf函数来接收字符了。因为scanf函数遇到空格会停止读取。我们可以用get…...

RAPTOR:树组织检索的递归抽象处理

RAPTOR: RECURSIVE ABSTRACTIVE PROCESSING FOR TREE-ORGANIZED RETRIEVAL Title&#xff1a;树组织检索的递归抽象处理 https://arxiv.org/pdf/2401.18059.pdf 摘要 检索增强语言模型可以更好的融入长尾问题&#xff0c;但是现有的方法只检索短的连续块&#xff0c;限制了整…...

图论:合适的环

4979. 合适的环 - AcWing题库 给定一个 n 个点 m 条边的无向图。 图中不含重边和自环。 请你在图中选出一个由三个点组成的环。 设图中一共有 x 条边满足&#xff1a;不在选择的环内&#xff0c;且与选择的环内某个点相连。 我们希望通过合理选环&#xff0c;使得 x 的值尽可能…...

【数据分享】1929-2023年全球站点的逐月平均降水量(Shp\Excel\免费获取)

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、湿度等指标&#xff0c;说到常用的降水数据&#xff0c;最详细的降水数据是具体到气象监测站点的降水数据&#xff01; 有关气象指标的监测站点数据&#xff0c;之前我们分享过1929-2023年全…...

React+Antd实现省、市区级联下拉多选组件(支持只选省不选市)

1、效果 是你要的效果&#xff0c;咱们继续往下看&#xff0c;搜索面板实现省市区下拉&#xff0c;原本有antd的Cascader组件&#xff0c;但是级联组件必须选到子节点&#xff0c;不能只选省&#xff0c;满足不了页面的需求 2、环境准备 1、react18 2、antd 4 3、功能实现 …...

CentOS镜像如何下载?在VMware中如何安装?

一、问题 CentOS镜像如何下载&#xff1f;在VMware中如何安装&#xff1f; 二、解决 1、CentOS镜像的下载 &#xff08;1&#xff09;官方网站 The CentOS Project &#xff08;2&#xff09;官方中文官网 CentOS 中文 官网 &#xff08;3&#xff09;选择CentOS Linux…...

计算机科学导论(4)DMA传输原理

文章目录 DMA的工作原理DMA的优势DMA的类型DMA的应用 DMA&#xff08;Direct Memory Access&#xff09;直接内存访问是一种允许某些硬件子系统在不通过中央处理单元&#xff08;CPU&#xff09;的情况下&#xff0c;直接从内存读取或向内存写入数据的技术。这种方式可以显著提…...

select、poll和epoll的区别

文章目录 概要一、多路复用I/O模型的诞生1.1 多线程或进程方式1.2 通过数组&#xff0c;链表等方式保存socket fd&#xff0c;不断轮询 二、select三、poll四、epoll五、小结六、参考 概要 在Unix五种I/O模型一文中&#xff0c;提到了I/O多路复用模型&#xff0c;其在Linux下有…...

gpt今日最新新闻:gpts的广泛应用

最近&#xff0c;OpenAI给ChatGPT带来了一个备受期待的更新——“GPT提及&#xff08;mentions&#xff09;”功能。这项创新不仅增强了ChatGPT的实用性&#xff0c;也为AI在日常业务中的运用开辟了新路径。在本文中&#xff0c;我将分享我对这项新功能的初步体验&#xff0c;并…...

【进入游戏行业选游戏特效还是技术美术?】

进入游戏行业选游戏特效还是技术美术&#xff1f; 游戏行业正处于蓬勃发展的黄金时期&#xff0c;科技的进步推动了游戏技术和视觉艺术的飞速革新。在这个创意和技术挑战交织的领域里&#xff0c;游戏特效和技术美术岗位成为了许多人追求的职业目标。 这两个岗位虽然紧密关联…...

(delphi11最新学习资料) Object Pascal 学习笔记---第4章第2.3节(常量参数)

4.2.3 常量参数 ​ 作为引用参数的替代&#xff0c;您可以使用const参数。由于您无法在例程内为const参数赋予新值&#xff0c;因此编译器可以优化参数传递。编译器可以选择与引用参数相似的方法&#xff08;或者在C术语中是const引用&#xff09;&#xff0c;但行为类似于值参…...

事件在状态流程图中的工作方式

什么是事件&#xff1f; 事件是一个Stateflow对象&#xff0c;它可以触发以下对象中一个动作&#xff1a; Simulink触发子系统 Simulink函数调用子系统 状态流程图 何时使用事件 当你想&#xff1a; 激活Simulink触发的子系统 激活Simulink函数调用子系统 在状态流程图…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...