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

Python算法题集_翻转二叉树

 Python算法题集_翻转二叉树

  • 题226:翻转二叉树
  • 1. 示例说明
  • 2. 题目解析
    • - 题意分解
    • - 优化思路
    • - 测量工具
  • 3. 代码展开
    • 1) 标准求解【DFS递归】
    • 2) 改进版一【BFS迭代,节点循环】
    • 3) 改进版二【BFS迭代,列表循环】
  • 4. 最优算法

本文为Python算法题集之一的代码示例

题226:翻转二叉树

1. 示例说明

  • 示例 1:

    在这里插入图片描述

    输入:root = [4,2,7,1,3,6,9]
    输出:[4,7,2,9,6,3,1]
    

    示例 2:

    在这里插入图片描述

    输入:root = [2,1,3]
    输出:[2,3,1]
    

    示例 3:

    输入:root = []
    输出:[]
    

    提示:

    • 树中节点数目范围在 [0, 100]
    • -100 <= Node.val <= 100

2. 题目解析

- 题意分解

  1. 本题为二叉树的翻转
  2. 基本的设计思路是深度优先算法【DFS(Depth-First Search)】、广度有限算法【BFS(Breadth-First Search)】

- 优化思路

  1. 通常优化:减少循环层次

  2. 通常优化:增加分支,减少计算集

  3. 通常优化:采用内置算法来提升计算速度

  4. 分析题目特点,分析最优解

    1. 可以考虑采用迭代法改写递归函数,提高性能

- 测量工具

  • 本地化测试说明:LeetCode网站测试运行时数据波动很大,因此需要本地化测试解决这个问题
  • CheckFuncPerf(本地化函数用时和内存占用测试模块)已上传到CSDN,地址:Python算法题集_检测函数用时和内存占用的模块
  • 本题本地化超时测试用例自己生成,详见【最优算法章节】

3. 代码展开

1) 标准求解【DFS递归】

采用深度优先算法,标准递归实现

马马虎虎,超过66%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def invertTree_base(self, root):if not root:return Noneroot.left, root.right = root.right, root.leftself.invertTree_base(root.left)self.invertTree_base(root.right)return rootaroot = generate_binary_tree(ilen)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.invertTree_base, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 invertTree_base 的运行时间为 600.12 ms;内存使用量为 4.00 KB 执行结果 = 71

2) 改进版一【BFS迭代,节点循环】

通过堆栈结构的迭代算法来改写递归算法,单次循环一个节点

性能良好,超过82%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def invertTree_ext1(self, root):if not root:return Nonestacktree = [root]while stacktree:tmpnode = stacktree.pop()tmpnode.left, tmpnode.right = tmpnode.right, tmpnode.leftif tmpnode.right:stacktree.append(tmpnode.right)if tmpnode.left:stacktree.append(tmpnode.left)return rootaroot = generate_binary_tree(ilen)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.invertTree_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 invertTree_ext1 的运行时间为 546.13 ms;内存使用量为 0.00 KB 执行结果 = 7

3) 改进版二【BFS迭代,列表循环】

通过队列结构的迭代算法来改写递归算法,每次循环一个批次,减少了部分循环判断计算

勉强通关,超过19%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def invertTree_ext2(self, root):if not root:return NonequeueTree = [root]while queueTree:for iIdx in range(len(queueTree)):tmpnode = queueTree.pop()tmpnode.left, tmpnode.right = tmpnode.right, tmpnode.leftif tmpnode.left:queueTree.append(tmpnode.left)if tmpnode.right:queueTree.append(tmpnode.right)return rootaroot = generate_binary_tree(ilen)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.invertTree_ext2, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 运行结果
函数 invertTree_ext2 的运行时间为 471.11 ms;内存使用量为 0.00 KB 执行结果 = 21

4. 最优算法

根据本地日志分析,最优算法为第3种方式【BFS迭代,列表循环】inorderTraversal_ext2

import random
ilen = 1000000
def generate_binary_tree(node_count):if node_count <= 0:return Noneroot = TreeNode(random.randint(1, 100))left = generate_binary_tree(node_count // 2)right = generate_binary_tree(node_count // 2)root.left = leftroot.right = rightreturn root
aroot = generate_binary_tree(ilen)
aSolution = Solution()
result = cfp.getTimeMemoryStr(Solution.invertTree_base, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))
aroot = generate_binary_tree(ilen)
result = cfp.getTimeMemoryStr(Solution.invertTree_ext1, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))
aroot = generate_binary_tree(ilen)
result = cfp.getTimeMemoryStr(Solution.invertTree_ext2, aSolution, aroot)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))# 算法本地速度实测比较
函数 invertTree_base 的运行时间为 600.12 ms;内存使用量为 4.00 KB 执行结果 = 71
函数 invertTree_ext1 的运行时间为 546.13 ms;内存使用量为 0.00 KB 执行结果 = 7
函数 invertTree_ext2 的运行时间为 471.11 ms;内存使用量为 0.00 KB 执行结果 = 21

一日练,一日功,一日不练十日空

may the odds be ever in your favor ~

相关文章:

Python算法题集_翻转二叉树

Python算法题集_翻转二叉树 题226&#xff1a;翻转二叉树1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【DFS递归】2) 改进版一【BFS迭代&#xff0c;节点循环】3) 改进版二【BFS迭代&#xff0c;列表循环】 4. 最优算法 本文为Python算法题集…...

Git快速掌握,通俗易懂

Git分布式版本控制工具 介绍 Git是一个开源的分布式版本控制系统&#xff0c;用于敏捷高效地处理任何或小或大的项目。Git是由Linus Torvalds为了帮助管理Linux内核开发而开发的一个开放源码的版本控制软件。Git可以帮助开发者们管理代码的版本&#xff0c;避免代码冲突&#…...

PHP毕业设计图片分享网站76t17

图片分享网站主要是为了提高工作人员的工作效率和更方便快捷的满足用户&#xff0c;更好存储所有数据信息及快速方便的检索功能&#xff0c;对系统的各个模块是通过许多今天的发达系统做出合理的分析来确定考虑用户的可操作性&#xff0c;遵循开发的系统优化的原则&#xff0c;…...

代码随想录 Leetcode45. 跳跃游戏 II

题目&#xff1a; 代码(首刷看解析 2024年2月15日&#xff09;&#xff1a; class Solution { public:int jump(vector<int>& nums) {if (nums.size() 1) return 0;int res 0;int curDistance 0;int nextDistance 0;for (int i 0; i < nums.size(); i) {nex…...

【C语言】socketpair 的系统调用

一、 Linux 内核 4.19socketpair 的系统调用 SYSCALL_DEFINE4(socketpair, int, family, int, type, int, protocol,int __user *, usockvec) {return __sys_socketpair(family, type, protocol, usockvec); } 这段代码定义了一个名为 socketpair 的系统调用。系统调用是操作…...

【论文精读】BERT

摘要 以往的预训练语言表示应用于下游任务时的策略有基于特征和微调两种。其中基于特征的方法如ELMo使用基于上下文的预训练词嵌入拼接特定于任务的架构&#xff1b;基于微调的方法如GPT使用未标记的文本进行预训练&#xff0c;并针对有监督的下游任务进行微调。 但上述两种策略…...

Codeforces Round 925 (Div. 3) - A、B、C、D、E

文章目录 前言A. Recovering a Small StringB. Make EqualC. Make Equal AgainD. Divisible PairsE. Anna and the Valentines Day Gift 前言 本篇博客是Codeforces Round 925周赛的A、B、C、D、E五题的题解 A. Recovering a Small String 可以通过sum的大小分为三种情况&#…...

快速部署MES源码/万界星空科技开源MES

什么是开源MES软件&#xff1f; 开源MES软件是指源代码可以免费获取、修改和分发的MES软件。与传统的商业MES软件相比&#xff0c;开源MES软件具有更高的灵活性和可定制性。企业可以根据自身的需求对软件进行定制化开发&#xff0c;满足不同生产环境下的特定需求。 开源MES软件…...

【Python网络编程之TCP三次握手】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;Python开发技术 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; Python网络编程之[TCP三次握手] 代码见资源&#xff0c;效果图如下一、实验要求二、协议原理2.…...

【leetcode】深搜、暴搜、回溯、剪枝(C++)2

深搜、暴搜、回溯、剪枝&#xff08;C&#xff09;2 一、括号生成1、题目描述2、代码3、解析 二、组合1、题目描述2、代码3、解析 三、目标和1、题目描述2、代码3、解析 四、组合总和1、题目描述2、代码3、解析 五、字母大小写全排列1、题目描述2、代码3、解析 六、优美的排列1…...

鸿蒙开发-UI-图形-图片

鸿蒙开发-UI-组件 鸿蒙开发-UI-组件2 鸿蒙开发-UI-组件3 鸿蒙开发-UI-气泡/菜单 鸿蒙开发-UI-页面路由 鸿蒙开发-UI-组件导航-Navigation 鸿蒙开发-UI-组件导航-Tabs 文章目录 一、基本概念 二、图片资源加载 1. 存档图类型数据源 2.多媒体像素图 三、显示矢量图 四、图片…...

.NET Core WebAPI中使用Log4net记录日志

一、安装NuGet包 二、添加配置 // log4net日志builder.Logging.AddLog4Net("CfgFile/log4net.config");三、配置log4net.config文件 <?xml version"1.0" encoding"utf-8"?> <log4net><!-- Define some output appenders -->…...

Nginx配置php留档

好久没有用过php了&#xff0c;近几日配置nginxphp&#xff0c;留档。 安装 ubunt下nginx和php都可以使用apt安装&#xff1a; sudo apt install nginx php8 如果想安装最新的php8.2,则需要运行下面语句&#xff1a; sudo dpkg -l | grep php | tee packages.txt sudo add-…...

英语题不会怎么搜答案?分享五个支持答案和解析的工具 #学习方法#媒体

在大学的学习过程中&#xff0c;我们常常会遇到一些难以解决的问题&#xff0c;有时候甚至会感到束手无策。然而&#xff0c;如今的技术发展给我们提供了新的解决方案。搜题软件作为一种强大的学习工具&#xff0c;正在被越来越多的大学生所接受和使用。今天&#xff0c;我将为…...

Rust 数据结构与算法:4栈:用栈实现进制转换

2、进展转换 将十进制数转换为二进制表示形式的最简单方法是“除二法”&#xff0c;可用栈来跟踪二进制结果。 除二法 下面实现一个将十进制数转换为二进制或十六进制的算法&#xff0c;代码如下&#xff1a; #[derive(Debug)] struct Stack<T> {size: usize, // 栈大…...

树莓派4B(Raspberry Pi 4B)使用docker搭建阿里巴巴sentinel服务

树莓派4B&#xff08;Raspberry Pi 4B&#xff09;使用docker搭建阿里巴巴sentinel服务 由于国内访问不了docker hub&#xff0c;而国内镜像仓库又没有适配树莓派ARM架构的sentinel镜像&#xff0c;所以我们只能退而求其次——自己动手构建镜像。本文基于Ubuntu&#xff0c;Jav…...

Django视图

HttpRequests对象 利用http协议向服务器传参的4种途径 提取url特定部分&#xff0c;如/web/index/&#xff0c;可以通过在服务器端的路由中用正则表达式截取查询字符串&#xff0c;形如?key1value&keyvalue2&#xff0c;&#xff08;&#xff1f;前面是路由&#xff0c;…...

python基本语法

变量无需声明 Python 中的变量不需要声明。每个变量在使用前都必须赋值&#xff0c;变量赋值以后该变量才会被创建。 在 Python 中&#xff0c;变量就是变量&#xff0c;它没有类型&#xff0c;我们所说的"类型"是变量所指的内存中对象的类型。 len800 #整型变…...

app逆向-⽹络请求库rxjava2

文章目录 一、前言二、安装三、GET请求实现四、POST请求实现 一、前言 RxJava 2 是一个流行的 Java 库&#xff0c;用于使用可观察序列组合异步和基于事件的程序。它是原始 RxJava 库的重新实现&#xff0c;旨在更高效并且更适合于 Java 8 及更高版本。 RxJava 2 的主要特性包…...

Spring Boot 笔记 007 创建接口_登录

1.1 登录接口需求 1.2 JWT令牌 1.2.1 JWT原理 1.2.2 引入JWT坐标 1.2.3 单元测试 1.2.3.1 引入springboot单元测试坐标 1.2.3.2 在单元测试文件夹中创建测试类 1.2.3.3 运行测试类中的生成和解析方法 package com.geji;import com.auth0.jwt.JWT; import com.auth0.jwt.JWTV…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...