Leetcode每日一题学习训练——Python3版(从二叉搜索树到更大和树)

版本说明

当前版本号[20231204]。

版本修改说明
20231204初版

目录

文章目录

  • 版本说明
  • 目录
  • 从二叉搜索树到更大和树
    • 理解题目
    • 代码思路
    • 参考代码

原题可以点击此 1038. 从二叉搜索树到更大和树 前去练习。

从二叉搜索树到更大和树

给定一个二叉搜索树 root (BST),请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

提醒一下, 二叉搜索树 满足下列约束条件:

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

示例 1:

img

输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2:

输入:root = [0,null,1]
输出:[1,null,1]

提示:

  • 树中的节点数在 [1, 100] 范围内。
  • 0 <= Node.val <= 100
  • 树中的所有值均 不重复

理解题目

1、每个节点的值替换成树中大于或者等于该节点值的所有节点值之和 ==》

用 4节点 举个例子: 比 4节点 大的有 5、6、7、8 节点

所以 4节点 所对应的值 :4 + 5 + 6 + 7 + 8 = 30

代码思路

  1. 它定义了一个名为Solution的类,其中包含一个名为bstToGst的方法。该方法接受一个根节点作为参数,并返回转换后的累加树的根节点。

    def bstToGst(self, root: TreeNode) -> TreeNode:
    
  2. bstToGst方法中,定义了一个名为dfs的内部函数,用于执行深度优先搜索。该函数接受一个节点作为参数,并使用递归的方式遍历整个树。

       # 定义一个深度优先搜索函数,用于遍历二叉搜索树
            def dfs(root: TreeNode):
    
  3. dfs函数中,首先声明了一个名为total的变量,用于存储当前节点的值加上其左子树中所有节点的值的总和。然后,通过递归调用dfs函数遍历右子树,将当前节点的值更新为total,并将total增加当前节点的值。最后,再次递归调用dfs函数遍历左子树。

      nonlocal total  # 声明total为非局部变量,以便在dfs函数内部修改它的值
                if root:
                    dfs(root.right)  # 先遍历右子树
                    total += root.val  # 累加当前节点的值
                    root.val = total  # 更新当前节点的值为累加和
                    dfs(root.left)  # 再遍历左子树
    
  4. 在主函数中,初始化了total变量为0,然后调用dfs(root)开始遍历整个树。最后,返回根节点作为转换后的累加树的根节点。

        total = 0  # 初始化累加和为0
        dfs(root)  # 调用深度优先搜索函数,从根节点开始遍历
        return root  # 返回转换后的二叉搜索树的根节点

参考代码

这段代码是一个解决**二叉搜索树(BST)转换为累加树(GST)**问题的Python类。

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        def dfs(root: TreeNode):
            nonlocal total
            if root:
                dfs(root.right)
                total += root.val
                root.val = total
                dfs(root.left)
        
        total = 0
        dfs(root)
        return root

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

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

相关文章

麦田医学CEO参加2023年度苏州市青年创业标兵授奖仪式

麦田医学CEO参加2023年度苏州市青年创业标兵授奖仪式 2023年12月4日&#xff0c;麦田&#xff08;苏州&#xff09;医学科技有限公司&#xff08;下简称麦田医学&#xff09;首席执行官&#xff08;CEO&#xff09;李任远同志受邀参加在苏州广电总台举行的2023年度苏州大学生创…

如何在亚马逊平台上找到最畅销的产品

这是您掌握在全球最大的在线市场上销售艺术的首选资源。在本博客中&#xff0c;我们将深入探讨在英国亚马逊上查找最畅销产品的秘密。在浩瀚的选择海洋中导航可能会令人不知所措&#xff0c;但不要害怕——有了正确的策略&#xff0c;您就可以发现利润丰厚的机会并提高销售额。…

C++ day53 最长公共子序列 不相交的线 最大子序和

题目1&#xff1a;1143 最长公共子序列 题目链接&#xff1a;最长公共子序列 对题目的理解 返回两个字符串的最长公共子序列的长度&#xff0c;如果不存在公共子序列&#xff0c;返回0&#xff0c;注意返回的是最长公共子序列&#xff0c;与前一天的最后一道题不同的是子序…

uniapp 在线预览PDF

1、官网地址&#xff1a; https://mozilla.github.io/pdf.js/getting_started/ 2、解压文件到static中 3、定义查看组件FilePreview <template><view><web-view :src"allUrl"></web-view></view> </template><script> e…

(04730)电路分析基础之电阻、电容及电感元件

04730电子技术基础 语雀&#xff08;完全笔记&#xff09; 电阻元件、电感元件和电容元件的概念、伏安关系&#xff0c;以及功率分析是我们以后分析电 路的基础知识。 电阻元件 电阻及其与温度的关系 电阻 电阻元件是对电流呈现阻碍作用的耗能元件&#xff0c;例如灯泡、…

mongoose学习记录

mongoose安装和连接数据库 npm i mongoose导入mongoose const mongoose require(mongoose) mongoose.set("strictQuery",true)连接数据库 mongoose.connect(mongodb:127.0.0.1:27017/test)设置回调 mongoose.connection.on(open,()>{console.log("连接成…

弱口令防护和网站防盗链有什么用

弱口令防护主要针对用户账户的安全。弱口令是指容易被猜测或破解的密码&#xff0c;如常见的密码、简单的数字序列或字典中的单词等。弱口令防护的目的是防止恶意用户或攻击者通过猜测或暴力破解密码的方式获取合法用户的账户权限。通过实施强密码策略、密码复杂度要求和账户锁…

centos 7.9 二进制部署 kubernetes 1.27.7

文章目录 1. 预备条件2. 基础配置2.1 配置root远程登录2.2 配置主机名2.3 安装 ansible2.4 配置互信2.5 配置hosts文件2.6 关闭防firewalld火墙2.7 关闭 selinux2.8 关闭交换分区swap2.9 修改内核参数2.10 安装iptables2.11 开启ipvs2.12 配置limits参数2.13 配置 yum2.14 配置…

【JavaEE进阶】 Spring核⼼与设计思想

文章目录 &#x1f332;Spring 是什么&#xff1f;&#x1f384;什么是IoC呢&#xff1f;&#x1f388;传统程序开发&#x1f388;传统程序开发的缺陷&#x1f388;如何解决传统程序的缺陷&#xff1f;&#x1f388;控制反转式程序开发&#x1f388;对⽐总结规律 &#x1f340;…

十二、FreeRTOS之FreeRTOS任务相关API函数

本节需要掌握以下内容&#xff1a; 1&#xff0c;FreeRTOS任务相关API函数介绍&#xff08;熟悉&#xff09; 2&#xff0c;任务状态查询API函数实验&#xff08;掌握&#xff09; 3&#xff0c;任务时间统计API函数实验&#xff08;掌握&#xff09; 4&#xff0c;课堂总结…

【鸿蒙应用开发】开发环境搭建及IDE安装使用

1.下载安装包 安装包下载地址&#xff1a; 点击跳转下载页面 可以根据自己的操作系统选择对应版本下载。 本文以Windows安装为例&#xff0c;Mac安装方式相同 2. 安装 下载好后&#xff0c;打开安装包&#xff0c;进入安装界面&#xff1a; 点击Next&#xff0c;进入安…

vue创建项目,使用可视化界面安装插件

安装项目&#xff1a; vue create vue-app 选择默认配置就行&#xff0c;也可以按需选择自定义配置 vue ui通过可视化管理项目 通过可视化安装全家桶插件

Spring Cloud 配置 Druid(二)

不废话&#xff0c;直接上代码&#xff0c; Nacos搭建的微服务&#xff0c;可以看Spring Cloud 配置 Nacos&#xff08;一&#xff09;-CSDN博客 一&#xff0c;pom文件 spring-cloud-starter-alibaba-nacos-discovery 和 spring-cloud-starter-openfeign 都是基于spring-cl…

95所双一流高校参与,“搜索界奥林匹克”决出28个获奖团队

只需要回答几个问题&#xff0c;就能生成个性化的简历&#xff0c;还提供优化建议&#xff0c;安排AI模拟面试。这样的效率神器&#xff0c;就出现第二届百度搜索创新大赛的赛场上。 &#x1f680; 来自南京航空航天大学的“肝到凌晨”团队&#xff0c;利用文心一言插件平台“…

【新手解答8】深入探索 C 语言:递归与循环的应用

C语言的相关问题解答 写在最前面问题&#xff1a;探索递归与循环在C语言中的应用解析现有代码分析整合循环示例代码修改注意事项结论 延伸&#xff1a;递归和循环的退出条件设置解析使用递归使用循环选择适合的方法 写在最前面 一位粉丝私信交流&#xff0c;回想起了当初的我C…

ORACLE使用Mybatis-plus批量插入

ORACLE使用mybatis-plus自带的iservice.saveBatch方法时&#xff0c;会报DML Returing cannot be batch错误&#xff1a; 推测原因是oracle不支持insert into table_name (,) values &#xff08;&#xff0c;&#xff09;,&#xff08;&#xff09;的写法。且oracle不会自动生…

【C语言】超详解,让你C语言成功入门(五)——操作符

目录 1.算术操作符2.移位操作符2.1左移操作符<<2.2右移操作符>> 3.位操作符4.赋值操作符5.单目操作符5.1单目操作符介绍5.2sizeof 和 数组 6.关系操作符7.逻辑操作符8.条件操作符&#xff08;三目操作符&#xff09;9.逗号表达式10.下标引用、函数调用和结构体11.表…

基于DotNetty实现一个接口自动发布工具 - 通信实现

基于 DotNetty 实现通信 DotNetty : 是微软的 Azure 团队&#xff0c;使用 C#实现的 Netty 的版本发布。是.NET 平台的优秀网络库。 项目介绍 OpenDeploy.Communication 类库项目,是通信相关基础设施层 Codec 模块实现编码解码 Convention 模块定义约定,比如抽象的业务 Handle…

华为手环 8 五款免费表盘已上线,请注意查收

华为手环 8&#xff0c;作为一款集时尚与实用于一体的智能手环&#xff0c;不仅具备强大的功能&#xff0c;还经常更新的表盘样式&#xff0c;让用户掌控时间与健康的同时&#xff0c;也能展现自己的时尚品味。这不&#xff0c;12 月官方免费表盘又上新了&#xff0c;推出了五款…

批量AI创作文案的工具,批量AI创作文章的软件

人工智能&#xff08;AI&#xff09;的应用不断拓展&#xff0c;其中批量AI创作逐渐成为许多文本创作者和企业编辑的热门选择。面对海量的文章需求&#xff0c;批量AI创作工具能够高效、快速地生成大量文本内容&#xff0c;从而减轻创作者的工作负担。本文将专心分享批量AI创作…