代码随想录算法训练营第十七天(py)| 二叉树 | 513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树

513.找树左下角的值

力扣链接
给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

思路 层序遍历

层序遍历之后,取最后一个数组的第一个元素

class Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:levels = []self.helper(root, 0, levels)return levels[-1][0]def helper(self, node, level, levels):if node == None:returnif len(levels)== level:levels.append([])levels[level].append(node.val)self.helper(node.left, level+1,levels)self.helper(node.right, level+1,levels)

112. 路径总和

力扣链接
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

思路

和二叉树的所有路径一样需要用到回溯,一直遍历到叶子节点,判断这一路上的和是否符合条件,如果不符合则回溯到上一个节点,以此重复。
判断和是否符合要求,可以用target递减的方式,判断最终结果是否为0

class Solution:def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:if root == None:return Falsereturn self.traversal(root, targetSum-root.val)def traversal(self, node, cnt):if node.left == None and node.right == None and cnt == 0: # 遇到叶子结点并且计数为0return Trueif node.left == None and node.right == None and cnt != 0: # 遇到叶子结点并且计数不为0return Falseif node.left:cnt -= node.left.valif self.traversal(node.left, cnt): return Truecnt += node.left.val # 回溯if node.right:cnt -= node.right.valif self.traversal(node.right, cnt): return Truecnt += node.right.val # 回溯return False

113. 路径总和II

力扣链接
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

思路

和上一题及二叉树的所有路径很像,为了避免参数混乱可以创建全局变量

class Solution:def __init__(self):self.result = []self.path = []def traversal(self, cur, count):if not cur.left and not cur.right and count == 0: # 遇到了叶子节点且找到了和为sum的路径self.result.append(self.path[:])returnif not cur.left and not cur.right: # 遇到叶子节点而没有找到合适的边,直接返回returnif cur.left: # 左 (空节点不遍历)self.path.append(cur.left.val)count -= cur.left.valself.traversal(cur.left, count) # 递归count += cur.left.val # 回溯self.path.pop() # 回溯if cur.right: #  右 (空节点不遍历)self.path.append(cur.right.val) count -= cur.right.valself.traversal(cur.right, count) # 递归count += cur.right.val # 回溯self.path.pop() # 回溯returndef pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:self.result.clear()self.path.clear()if not root:return self.resultself.path.append(root.val) # 把根节点放进路径self.traversal(root, sum - root.val)return self.result 

106.从中序与后序遍历序列构造二叉树

力扣链接
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

思路

在这里插入图片描述
第一步:如果数组大小为零的话,说明是空节点了。

第二步:如果不为空,那么取后序数组最后一个元素作为根节点元素。

第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点

第四步:切割中序数组,切成中序左数组和中序右数组 (顺序别搞反了,一定是先切中序数组)

第五步:切割后序数组,切成后序左数组和后序右数组

第六步:递归处理左区间和右区间

class Solution:def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:# 1.判断是否空if postorder == []:return None# 2.后序遍历的最后一个是当前中间节点root_val = postorder[-1]root = TreeNode(root_val)# 3.切割点separtor_idx = inorder.index(root_val)# 4.切分inorderinorder_l = inorder[:separtor_idx]inorder_r = inorder[separtor_idx+1:]# 5.切分postorderpostorder_l = postorder[:len(inorder_l)]postorder_r = postorder[len(inorder_l):len(postorder)-1]# 6.递归root.left = self.buildTree(inorder_l, postorder_l)root.right = self.buildTree(inorder_r, postorder_r)return root

105.从前序与中序遍历序列构造二叉树

力扣链接
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

思路

与上一题思路类似
第一步:如果数组大小为零的话,说明是空节点了。

第二步:如果不为空,那么取前序数组第一个元素作为根节点元素。

第三步:找到前序数组第一个元素在中序数组中的位置,作为切割点

第四步:切割中序数组,切成中序左数组和中序右数组

第五步:切割前序数组,切成前序左数组和前序右数组

第六步:递归处理左区间和右区间

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:# 1.判断是否为空if inorder == []:return None# 2.前序遍历的第一个是当前中间节点root_val = preorder[0]root = TreeNode(root_val)# 3.切割点separtor_idx = inorder.index(root_val)# 4.切分inorderinorder_l = inorder[:separtor_idx]inorder_r = inorder[separtor_idx+1:]# 5.切分preorderpreorder_l = preorder[1:1+len(inorder_l)]preorder_r = preorder[1+len(inorder_l):]# 6.递归root.left = self.buildTree(preorder_l,inorder_l)root.right = self.buildTree(preorder_r,inorder_r)return root

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

深入解析编程逻辑中的关键字与逻辑运算

新书上架~👇全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我👆,收藏下次不迷路┗|`O′|┛ 嗷~~ 目录 一、认识关键字及其重要性 二、逻辑运算的关键字 1. and、or 和 not 的运用 2. 逻辑运算的…

世界上首位AI程序员诞生,AI将成为人类的对手吗?

3月13日,世界上第一位AI程序员Devin诞生,不仅能自主学习新技术,自己改Bug,甚至还能训练和微调自己的AI模型,表现已然远超GPT-4等“顶流选手”。 AI的学习速度如此之快,人类的教育能否跟上“机器学习”的速…

【C++算法】BFS解决单源最短路问题相关经典算法题

1.迷宫中离入口最近的出口 首先我们可以将这道题目简化一下,可以往我们这一章的主题上面来想想。 我们利层序遍历来解决最短路径问题,是最经典的做法。我们可以从起点开始层序遍历, 并组在遍历的过程中记录当前遍历的层数。这样就能在找到出口的时候&…

人工智能应用-实验7-胶囊网络分类minst手写数据集

文章目录 🧡🧡实验内容🧡🧡🧡🧡代码🧡🧡🧡🧡分析结果🧡🧡🧡🧡实验总结🧡🧡 &#x1f9…

缓存IO与直接IO

IO类型 缓存 I/O 缓存 I/O 又被称作标准 I/O,大多数文件系统的默认 I/O 操作都是缓存 I/O。在 Linux 的缓存 I/O 机制中,数据先从磁盘复制到内核空间的缓冲区,然后从内核空间缓冲区复制到应用程序的地址空间(用户空间&#xff0…

常见 JVM 面试题补充

原文地址 : 26 福利:常见 JVM 面试题补充 (lianglianglee.com) CMS 是老年代垃圾回收器? 初步印象是,但实际上不是。根据 CMS 的各个收集过程,它其实是一个涉及年轻代和老年代的综合性垃圾回收器。在很多文章和书籍的划分中&…

Hive运行错误

Hive 文章目录 Hive错误日志错误SessionHiveMetaStoreClientql.Driver: FAILED: Execution Error, return code 2 from org.apache.hadoop.hive.ql.exec.mr.MapRedTaskerror: Could not find or load main class org.apache.hadoop.mapreduce.v2.app.MRAppMaster Please check …

三、自定义信号和槽函数(无参和有参)

需求: 下班后,小明说请小红吃好吃的,随便吃,吃啥买啥 无参:小红没有提出吃啥 有参:小红提出自己想吃的东西,吃啥取决于一时兴起(emit触发) 思路: 1&#xff…

【高时效通路】

一 高时效通路 1.1 pathchdumper 实时数据拉取、实时数据处理、5分钟微批dump来加速时效性,具体来说: 实时数据拉取(Fetcher):基于Databus Fetcher基建,直接对接F0层实时拉取最新数据,保证该…

电脑键盘如何练习盲打?

电脑键盘如何练习盲打?盲打很简单,跟着我做,今天教会你。 请看【图1】: 【图1】中,红色方框就是8个基准键位,打字时我们左右手的8个手指就是放在这8个基准键位上,F键和J键上各有一个小突起&…

AcW木棒-XMUOJ恢复破碎的符咒木牌-DFS与剪枝

题目 思路 话不多说,直接上代码 代码 /* AcW木棒-XMUOJ恢复破碎的符咒木牌 搜索顺序:从小到大枚举最终的长度 len从前往后依次拼每根长度为len的木棍 优化: 1.优化搜索顺序:优先选择深度短的来搜索,故从大到小去枚…

Java——简易图书管理系统

本文使用 Java 实现一个简易图书管理系统 一、思路 简易图书管理系统说白了其实就是 用户 与 图书 这两个对象之间的交互 书的属性有 书名 作者 类型 价格 借阅状态 而用户可以分为 普通用户 管理员 使用数组将书统一管理起来 用户对这个数组进行操作 普通用户可以进…

Python简介

Python简介 1. Python定义 Python 是一种简单易学并且结合了解释性、编译性、互动性和面向对象的脚本语言。Python提供了高级数据结构,它的语法和动态类型以及解释性使它成为广大开发者的首选编程语言。 Python 是解释型语言: 开发过程中没有了编译这个环…

Android Gradle开发、应用、插件发布(六)—实现打包自动复制文件插件

1. 前言 项目中遇到了一个问题 : 其中一个模块MyLibrary的assets文件夹中,需要存放很多文件(每个文件对应一个功能)。 这样导致的问题是MyLibrary打出的这个aar包体积特别大。 如果把MyLibrary严谨地拆解成若干个Module又比较费时,对于现在业务现状来…

Vue3实战笔记(42)—Vue + ECharts:流量数据可视化的强大组合

文章目录 前言vue3使用echarts标准demo:总结 前言 在前端开发中,数据可视化已经成为了一个不可或缺的部分。Vue.js作为一个轻量级且易于上手的渐进式JavaScript框架,与ECharts这个强大的数据可视化库的结合,使得在Vue应用中构建交…

Mysql插入中文内容报错解决及其Mysql常用的存储引擎说明

一、问题描述 我们在Mysql数据库的表中插入带有中文内容时报错,提示【1366 - Incorrect string value: \xE5\x8C\x97\xE4\xBA\xAC... for column UserDealer at row 1】,如下图所示: 二、问题分析 一般来说插入中文内容有问题我们首先想到的就是编码问题;我们可以查看该表使…

文科论文,使用AI写作时能够提供实证数据吗?

人工智能时代,为了撰写论文提供思路及高效,利用AI撰写论文已是常态,可撰写文科论文通常研究中都需要实证数据,而AI撰写论文时能够提供这样的数据吗? 一、什么是实证数据 实证数据是指从研究报告、财务报表、新闻报道…

栈和队列的经典例题,LeetCode 括号匹配问题;栈实现队列;队列实现栈;队列带环问题

1.前序 又有很久没有更新文章了&#xff0c;这次带你们手撕几道基础题&#xff1b;真的就和康纳吃饭一样简单&#xff01;&#xff01;&#xff01; 如果还不会队列和栈的可以去看看之前写的博客&#xff1b; 栈的实现 队列概念以及实现 <- 快速传送 目录 1.前序 …

Jmeter例题分析-作业一

作业 作业1概要 本文档是关于执行软件性能测试的详细指南&#xff0c;包括使用JMeter工具进行测试的步骤和要求。 文档分为两个主要部分&#xff1a;性能测试的执行和性能测试报告的编写。 在第一部分中&#xff0c;详细描述了如何使用 JMeter进行性能测试。这包括设置测试环…

【机器学习】大模型在机器学习中的应用:从深度学习到生成式人工智能的演进

&#x1f512;文章目录&#xff1a; &#x1f4a5;1.引言 ☔2.大模型概述 &#x1f6b2;3.大模型在深度学习中的应用 &#x1f6f4;4.大模型在生成式人工智能中的应用 &#x1f44a;5.大模型的挑战与未来展望 &#x1f4a5;1.引言 随着数据量的爆炸性增长和计算能力的提…