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

日拱一卒(18)——leetcode学习记录:二叉树中的伪回文路径

一、题目

给你一棵二叉树,每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的,当它满足:路径经过的所有节点值的排列中,存在一个回文序列。

请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。

二、思路

  1. 理解伪回文路径的概念

    • 首先,我们要明白什么是伪回文路径。对于一条从根节点到叶节点的路径,这条路径上的节点值组成一个序列。如果这个序列可以通过重新排列,变成一个回文序列,那么这条路径就是伪回文路径。
    • 回文序列就是正读和反读都一样的序列,比如 "aba" 或 "aabb"。对于我们的问题,节点值范围是 1 到 9,所以我们只需要关注这些数字出现的次数。
    • 对于一个序列要成为伪回文序列,其中最多只能有一个数字出现的次数是奇数,其他数字出现的次数都必须是偶数。例如,对于序列 "121",数字 1 出现两次(偶数次),数字 2 出现一次(奇数次),可以重新排列成 "112" 形成回文,所以是伪回文序列;对于序列 "123",三个数字都只出现一次,不满足最多一个数字出现奇数次,所以不是伪回文序列。
  2. 使用深度优先搜索(DFS)遍历二叉树

    • 我们要遍历二叉树从根节点到所有叶节点的路径。这就像走迷宫一样,从起点(根节点)出发,每次选择一个分支(左子节点或右子节点)走,直到走到终点(叶节点)。
    • 在走的过程中,我们要记录下经过的节点值。
    • 当到达叶节点时,检查这条路径是否是伪回文路径。
  3. 记录节点值的出现次数

    • 我们可以使用一个列表(或数组)来记录每个数字(1 到 9)出现的次数。开始时,列表中所有数字的计数都是 0。
    • 当我们经过一个节点时,就把该节点值对应的计数加 1。
    • 当我们回溯(从叶节点往回走)时,要把这个计数减 1,因为我们要检查其他可能的路径。
  4. 检查是否是伪回文路径

    • 当到达叶节点时,我们检查记录节点值出现次数的列表。
    • 计算列表中出现奇数次的数字的数量。如果这个数量小于等于 1,那么这条路径就是伪回文路径。

具体步骤:

  1. 开始 DFS 遍历

    • 从根节点开始,将根节点的值对应的计数加 1。
    • 然后递归地对左子节点和右子节点进行 DFS 遍历。
    • 每次递归调用时,会重复上述加计数的操作。
  2. 到达叶节点

    • 当到达叶节点时,检查列表中出现奇数次的数字的数量。
    • 如果这个数量小于等于 1,说明这条路径是伪回文路径,我们可以将结果加 1。
  3. 回溯操作

    • 在从叶节点往回走时,要把当前节点值对应的计数减 1,这样可以继续检查其他可能的路径。

三、题解

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution:

    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:

        mylist = [0]*10

        return self.dfs(mylist,root)

    # 递归

    def dfs(self,mylist,root):

        ans = 0

        # 初始条件

        if not root:

            return 0

        mylist[root.val] += 1

        if not root.left and not root.right:

            ans = int(self.isPalindromic(mylist))

        else:  

            ans = self.dfs(mylist,root.left) + self.dfs(mylist,root.right)

        mylist[root.val] -= 1

        return ans

    def isPalindromic(self,mylist):

        odd = 0

        for value in mylist:

            if value%2 == 1:

                odd += 1

        return odd <= 1

相关文章:

日拱一卒(18)——leetcode学习记录:二叉树中的伪回文路径

一、题目 给你一棵二叉树&#xff0c;每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的&#xff0c;当它满足&#xff1a;路径经过的所有节点值的排列中&#xff0c;存在一个回文序列。 请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。 二、思路 …...

hive—炸裂函数explode/posexplode

1、Explode炸裂函数 将hive某列一行中复杂的 array 或 map 结构拆分成多行&#xff08;只能输入array或map&#xff09; 语法&#xff1a; select explode(字段) as 字段命名 from 表名; 举例&#xff1a; 1&#xff09;explode(array)使得结果中将array列表里的每个元素生…...

SpringBoot 新特性

优质博文&#xff1a;IT-BLOG-CN 2.1.0新特性最低支持jdk8,支持tomcat9 对响应式编程的支持&#xff0c;spring-boot-starter-webflux starter POM可以快速开始使用Spring WebFlux&#xff0c;它由嵌入式Netty服务器支持 1.5.8 2.1.0/2.7.0/3.0.0 Configuration propertie…...

鸿蒙app封装 axios post请求失败问题

这个问题是我的一个疏忽大意&#xff0c;在这里记录一下。如果有相同问题的朋友&#xff0c;可以借鉴。 当我 ohpm install ohos/axios 后&#xff0c;进行简单post请求验证&#xff0c;可以请求成功。 然后&#xff0c;我对axios 进行了封装。对axios 添加请求拦截器/添加响…...

消息队列 Kafka 架构组件及其特性

Kafka 人们通常有时会将 Kafka 中的 Topic 比作队列&#xff1b; 在 Kafka 中&#xff0c;数据是以主题&#xff08;Topic&#xff09;的形式组织的&#xff0c;每个 Topic 可以被分为多个分区&#xff08;Partition&#xff09;。每个 Partition 是一个有序的、不可变的消息…...

网络攻击与防范

目录 选填 第一章 1、三种网络模式 2、几种创建网络拓扑结构 NAT模式 VPN模式 软路由模式1 软路由模式2 3、Linux网络配置常用指令 4、常见网络服务配置 DHCP DNS Web服务与FTP服务 FTP用户隔离 第二章 DNS信息收集&#xff08;dnsenum、dnsmap&#xff09; 路…...

文献研读|基于像素语义层面图像重建的AI生成图像检测

前言&#xff1a;本篇文章主要对基于重建的AI生成图像检测的四篇相关工作进行介绍&#xff0c;分别为基于像素层面重建的检测方法 DIRE 和 Aeroblade&#xff0c;以及基于语义层面重建的检测方法 SimGIR 和 Zerofake&#xff1b;并对相应方法进行比较。 相关文章&#xff1a;论…...

【操作系统】为什么需要架构裁剪?

为什么需要架构裁剪&#xff1f; 原因 减小核心大小提高架构初始化速度降低内存占用提高系统性能移除不需要的功能&#xff0c;增加安全性 裁剪方法 初始化配置设置功能模块化移除不需要的驱动底层 一般裁剪对象&#xff08;以操作系统为例&#xff09; 文件系统的支持网…...

LSTM长短期记忆网络

LSTM&#xff08;长短期记忆网络&#xff09;数学原理 LSTM&#xff08;Long Short-Term Memory&#xff09;是一种特殊的递归神经网络&#xff08;RNN&#xff09;&#xff0c;解决了标准RNN中存在的梯度消失&#xff08;Vanishing Gradient&#xff09; 和**梯度爆炸&#x…...

基于前端技术UniApp和后端技术Node.js的电影购票系统

文章目录 摘要Abstruct第一章 绪论1.1 研究背景与意义1.2 国内外研究现状 第二章 需求分析2.1 功能需求分析2.2 非功能性需求分析 第二章系统设计3.1 系统架构设计3.1.1 总体架构3.1.2 技术选型 3.2 功能架构 第四章 系统实现4.1 用户端系统实现4.1.1 用户认证模块实现4.1.2 电…...

数据结构与算法:稀疏数组

前言 此文以整型元素的二维数组为例&#xff0c;阐述稀疏数组的思想。其他类型或许有更适合压缩算法或者其他结构的稀疏数组&#xff0c;此文暂不扩展。 稀疏数组的定义 在一个二维数据数组里&#xff0c;由于大量的元素的值为同一个值&#xff0c;比如 0或者其他已知的默认值…...

Meta重磅发布Llama 3.3 70B:开源AI模型的新里程碑

在人工智能领域&#xff0c;Meta的最新动作再次引起了全球的关注。今天&#xff0c;我们见证了Meta发布的Llama 3.3 70B模型&#xff0c;这是一个开源的人工智能模型&#xff0c;它不仅令人印象深刻&#xff0c;而且在性能上达到了一个新的高度。 一&#xff0c;技术突破&#…...

VSCode中的Black Formatter没有生效的解决办法

说明 如果正常按照配置进行的话&#xff0c;理论上是可以生效的。 "[python]": {"editor.defaultFormatter": "ms-python.black-formatter","editor.formatOnSave": true }但我在一种情况下发现不能生效&#xff0c;应为其本身的bug…...

【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题

目录 背包问题简介 问题描述 输入&#xff1a; 输出&#xff1a; 动态规划解法 动态规划状态转移 代码实现 代码解释 动态规划的时间复杂度 例子解析 输出&#xff1a; 总结 作者我蓝桥杯&#xff1a;2023第十四届蓝桥杯国赛C/C大学B组一等奖&#xff0c;所以请听我…...

Odoo:免费开源ERP的AI技术赋能出海企业电子商务应用介绍

概述 伴随电子商务的持续演进&#xff0c;客户对于便利性、速度以及个性化服务的期许急剧攀升。企业务必要探寻创新之途径&#xff0c;以强化自身运营&#xff0c;并优化购物体验。达成此目标的最为行之有效的方式之一&#xff0c;便是将 AI 呼叫助手融入您的电子商务平台。我们…...

微信小程序苹果手机自带的数字键盘老是弹出收起,影响用户体验,100%解决

文章目录 1、index.wxml2、index.js3、index.wxss1、index.wxml <!--index.wxml--> <view class="container"><view class="code-input-container"><view class="code-input-boxes"><!-- <block wx:for="{{…...

sql中case when若条件重复 执行的顺序

sql case when若条件重复 执行的顺序 在 SQL 中&#xff0c;如果你在 CASE 表达式中定义了多个 WHEN 子句&#xff0c;并且这些条件有重叠&#xff0c;那么 CASE 表达式的执行顺序遵循以下规则&#xff1a; &#xff08;1&#xff09;从上到下&#xff1a;SQL 引擎会按照 CASE …...

压力测试Jmeter简介

前提条件&#xff1a;要安装JDK 若不需要了解&#xff0c;请直接定位到左侧目录的安装环节。 1.引言 在现代软件开发中&#xff0c;性能和稳定性是衡量系统质量的重要指标。为了确保应用程序在高负载情况下仍能正常运行&#xff0c;压力测试变得尤为重要。Apache JMeter 是一…...

cesium 与 threejs 对比

Cesium 和 Three.js 都是用于在 Web 浏览器中创建和渲染 3D 图形的强大 JavaScript 库&#xff0c;但它们有显著的不同之处&#xff0c;主要体现在应用领域、功能集和使用场景上。 以下是两者之间的对比&#xff1a; 1. 应用场景 Three.js: 适用于广泛的 3D 图形应用&#xff…...

探索QScreen的信号与槽:动态响应屏幕变化

在处理屏幕显示和多显示器环境时&#xff0c;QScreen 提供了一些特有的信号&#xff0c;这些信号可以在屏幕的变化时通知应用程序&#xff0c;帮助我们动态地适配和响应显示设备的变化。今天&#xff0c;我们将深入探讨如何使用 QScreen 的信号与槽&#xff0c;并展示适用的使用…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...