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.val
    while queue_record:
        level_size = len(queue_record)
        for i in range(level_size):
            node = queue_record.pop(0)
            if i==0:
                res = node.val
            if 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 None

        queue = [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 = None
        self.traversal(root, 0)
        return self.result
    
    def traversal(self, node, depth):
        if not node.left and not node.right:
            if depth > self.max_depth:
                self.max_depth = depth
                self.result = node.val
            return
        
        if 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
    
    # 如果是叶子节点,检查目标和是否为0
    if 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 False

    stack_record = [(root, root.val)]

    while stack_record:
        node, value = stack_record.pop()
        if not node.left and not node.right:
            if value == targetSum:
                return True
        else:
            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 result
    
    def 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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/376115.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Quicker读取浏览器的书签(包括firefox火狐)

从edge换了火狐,但是quicker不能读取本地的bookmarks文件了,就研究了一下。 方法1:读取本地Bookmarks文件(仅谷歌内核浏览器) 谷歌内核的浏览器本地会有Bookmarks文件,放了所有的书签数据,直接…

新版MQL语言程序设计:键盘快捷键交易的设计与实现

文章目录 一、什么是快捷键交易二、使用快捷键交易的好处三、键盘快捷键交易程序设计思路四、键盘快捷键交易程序具体实现1.界面设计2.键盘交易事件机制的代码实现 一、什么是快捷键交易 操盘中按快捷键交易是指在股票或期货交易中,通过使用快捷键来进行交易操作的…

故障诊断 | 一文解决,TCN时间卷积神经网络模型的故障诊断(Matlab)

效果一览 文章概述 故障诊断 | 一文解决,TCN时间卷积神经网络模型的故障诊断(Matlab) 模型描述 时间卷积神经网络(TCN)是一种用于序列数据建模和预测的深度学习模型。它通过卷积操作在时间维度上对序列数据进行特征提取,并且可以处理可变长度的输入序列。 要使用TCN进行…

昆仑万维发布天工 2.0 大语言模型及AI助手App;AI成功破解2000年前碳化古卷轴

🦉 AI新闻 🚀 昆仑万维发布天工 2.0 大语言模型及AI助手App 摘要:昆仑万维近日推出了新版MoE大语言模型“天工 2.0”和相应的“天工 AI 智能助手”App,宣称为国内首个面向C端用户免费的基于MoE架构的千亿级参数大模型应用。天工…

购物车底部工具栏全选、总价、总数量实现

购物车商品加一个checked属性 定义allChecked属性 <!-- 底部工具栏 开始 --> <view class"footer_tool"><!-- 全选 开始 --><view class"all_chk_wrap"><checkbox-group><checkbox checked"{{allChecked}}">…

视频上传 - 断点续传那点事

在上一篇文章中&#xff0c;我们讲解了分片上传的实现方式。在讲解断点续传之前&#xff0c;我要把上篇文章中留下的问题讲解一下。读过上一篇文章的小伙伴们都知道&#xff0c;对于分片上传来说&#xff0c;它的传输方式分为2种&#xff0c;一种是按顺序传输&#xff0c;一种是…

如何安装x11vnc并结合cpolar实现win远程桌面Deepin

文章目录 1. 安装x11vnc2. 本地远程连接测试3. Deepin安装Cpolar4. 配置公网远程地址5. 公网远程连接Deepin桌面6. 固定连接公网地址7. 固定公网地址连接测试 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通俗易懂&#xff…

机器学习系列——(十六)回归模型的评估

引言 在机器学习领域&#xff0c;回归模型是一种预测连续数值输出的重要工具。无论是预测房价、股票价格还是天气温度&#xff0c;回归模型都扮演着不可或缺的角色。然而&#xff0c;构建模型只是第一步&#xff0c;评估模型的性能是确保模型准确性和泛化能力的关键环节。本文…

微信小程序解决华为手机保存图片到相册失败

1.新增隐私设置 2.优化代码 新增uni.authorize判断 _saveCode() {let that this;console.log(点击了保存图片)console.log(this.result)uni.authorize({scope: scope.writePhotosAlbum,success(e) {console.log(e)if (this.result ! "") {uni.saveImageToPhotosAlb…

github使用问题汇总

1. Permission denied 1.1. 问题描述 Permission denied (publickey). fatal: Could not read from remote repository. 1.2. 解决方法 生成公钥 ssh-keygen -t ed25519 -C "your_emailexample.com" 点击回车三次 Generating public/private ed25519 key pair. …

使用Nginx搭建旁路服务器获取客户端真实IP

一、前言 在实际业务开发过程中&#xff0c;很多时候有记录客户端真实IP的需求&#xff0c;但是从客户端发送的请求往往会经过很多代理服务器&#xff0c;导致后端服务获取的IP为代理以后的IP&#xff0c;不具有业务含义。为了解决这个问题&#xff0c;可以搭建一个旁路服务器…

上海亚商投顾:沪指涨超3% 深成指和创指双双飙涨超6%

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 今日A股三大指数一改近期低迷状态&#xff0c;早盘小幅低开后一路高歌猛进集体大涨&#xff0c;沪指涨超3%&am…

YUM | 包安装 | 管理

YUM 功能 软件包安装&#xff1a; 通过yum命令安装软件包。例如&#xff0c;安装一个名为 example-package 的软件包 yum install example-package更新包 检查更新&#xff1a; 检查可用更新&#xff1a; sudo yum check-update <package_name>软件包更新&#xff1a; y…

dolphinscheduler海豚调度(一)简介快速体验

1、简介 Apache DolphinScheduler 是一个分布式易扩展的可视化DAG工作流任务调度开源系统。适用于企业级场景&#xff0c;提供了一个可视化操作任务、工作流和全生命周期数据处理过程的解决方案。 Apache DolphinScheduler 旨在解决复杂的大数据任务依赖关系&#xff0c;并为应…

AI助力农作物自动采摘,基于DETR(DEtection TRansformer)开发构建作物生产场景下番茄采摘检测计数分析系统

去年十一那会无意间刷到一个视频展示的就是德国机械收割机非常高效自动化地24小时不间断地在超广阔的土地上采摘各种作物&#xff0c;专家设计出来了很多用于采摘不同农作物的大型机械&#xff0c;看着非常震撼&#xff0c;但是我们国内农业的发展还是相对比较滞后的&#xff0…

计算机视觉 | OpenCV 实现手势虚拟控制亮度和音量

Hi&#xff0c;大家好&#xff0c;我是半亩花海。在当今科技飞速发展的时代&#xff0c;我们身边充斥着各种智能设备&#xff0c;然而&#xff0c;如何更便捷地与这些设备进行交互却是一个不断被探索的课题。本文将主要介绍一个基于 OpenCV 的手势识别项目&#xff0c;通过手势…

基于Java学生管理系统设计与实现(源码+部署文档)

博主介绍&#xff1a; ✌至今服务客户已经1000、专注于Java技术领域、项目定制、技术答疑、开发工具、毕业项目实战 ✌ &#x1f345; 文末获取源码联系 &#x1f345; &#x1f447;&#x1f3fb; 精彩专栏 推荐订阅 &#x1f447;&#x1f3fb; 不然下次找不到 Java项目精品实…

解锁阿里巴巴面试题:创建线程的几种方式?

大家好,我是小米!今天我们来聊一个热门话题——阿里巴巴面试题:创建线程的几种方式。在技术的海洋中,线程是我们编程航程中的一艘不可或缺的船,驶向程序的未知领域。那么,究竟有哪些方式可以创建线程呢?让我们一起揭开这个技术的神秘面纱! 实现Runnable接口 首先,我…

最好的方式来预测未来是去创造它。

在辅导企业的过程中&#xff0c;对于「建设性的冲突」持开放态度&#xff0c;这背后反映了一种深刻的系统思考和变革管理的理念。在许多传统工作环境中&#xff0c;「和谐」往往被高度重视&#xff0c;但这种表面的和谐有时会掩盖问题的真相&#xff0c;阻碍组织的深层次变革和…

C语言:整形存储

#include<stdio.h> int main() {char a -1;signed char b -1;unsigned char c -1;printf("a%d,b%d,c%d", a, b, c);return 0; } b与a都是有符号数结果一样。a的signed相当于省略了。 运行结果 整形提升&#xff1a;整形算术运算总是以至少以缺省整型类型的精…