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

python coding with ChatGPT 打卡第15天| 二叉树:翻转二叉树、对称二叉树

相关推荐
python coding with ChatGPT 打卡第12天| 二叉树:理论基础
python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历
python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历

文章目录

  • 翻转二叉树
    • Key Points
    • 相关题目
    • 视频讲解
    • 重点分析
      • 递归遍历
      • 层序遍历
  • 对称二叉树
    • Key Points
    • 相关题目
    • 视频讲解
    • 重点分析
      • 递归法
      • 迭代法

翻转二叉树

Key Points

  1. 只要把每个节点的左右孩子翻转一下,就可以达到整体翻转的效果
  2. 可选择深度优先遍历(递归遍历)或广度优先遍历(层序遍历)

相关题目

226. 翻转二叉树

视频讲解

翻转二叉树

重点分析

递归遍历

前序:

def invertTreePreOrder(root):if not root:return Noneroot.left, root.right = root.right, root.leftinvertTreePreOrder(root.left)invertTreePreOrder(root.right)return root

中序:

def invertTreeInOrder(root):if not root:return NoneinvertTreeInOrder(root.left)root.left, root.right = root.right, root.leftinvertTreeInOrder(root.left)  # 注意:这里应该再次调用左子树return root

在中序遍历中,我们先递归地处理左子树,然后交换当前节点的左右子节点,最后处理右子树。注意,由于我们在交换后再递归右子树,实际上我们需要两次递归左子树。

中序 法2:

def invertTree(root):if not root:return rootright = root.right  # 先把右子树存起来# 左invertTree(root.left)# 根root.left, root.right = root.right, root.left# 右invertTree(right)return root

后序:

def invertTreePostOrder(root):if not root:return NoneinvertTreePostOrder(root.left)invertTreePostOrder(root.right)root.left, root.right = root.right, root.leftreturn root

层序遍历

def inverTree(root):if not root:return rootqueque_record = [root]while queque_record:node = queque_record.pop(0)node.left, node.right = node.right, node.left  # 这里不管是先翻转左右节点还是先加入左右节点都可以if node.left:queque_record.append(node.left)if node.right:queque_record.append(node.right)return root

在这里插入图片描述

在实现迭代法的过程中,有同学问了:递归与迭代究竟谁优谁劣呢?

从时间复杂度上其实迭代法和递归法差不多(在不考虑函数调用开销和函数调用产生的堆栈开销),但是空间复杂度上,递归开销会大一些,因为递归需要系统堆栈存参数返回值等等。

递归更容易让程序员理解,但收敛不好,容易栈溢出。

这么说吧,递归是方便了程序员,难为了机器(各种保存参数,各种进栈出栈)。

在实际项目开发的过程中我们是要尽量避免递归!因为项目代码参数、调用关系都比较复杂,不容易控制递归深度,甚至会栈溢出。

对称二叉树

Key Points

二叉树类的题目,确定遍历顺序非常重要

相关题目

101. 对称二叉树

视频讲解

同时操作两个二叉树

重点分析

递归法

def isSymmetric(root):if not root:return Truereturn compare(root.left, root.right)def compare(left, right):if not left and not right:return Trueif not left:return Falseif not right:return Falseif left.val != right.val:return Falsecon1 = compare(left.left, right.right)con2 = compare(left.right, right.left)if con1 and con2:return Truereturn False

在这里插入图片描述

迭代法

使用栈

def isSymmetric(root):if not root:return Truestack_record = [(root.left, root.right)]while stack_record:left, right = stack_record.pop()if not left and not right:continue   # 不能直接return Trueif not left:return Falseif not right:return Falseif left.val != right.val:return Falsestack_record.append([left.left, right.right])stack_record.append([left.right, right.left])return True

使用队列:

def isSymmetric(root):if not root:return Truequeue_record = [(root.left, root.right)]while queue_record:left, right = queue_record.pop(0)if not left and not right:continue   # 不能直接return Trueif not left:return Falseif not right:return Falseif left.val != right.val:return Falsequeue_record.append([left.left, right.right])queue_record.append([left.right, right.left])return True

在这里插入图片描述

相关文章:

python coding with ChatGPT 打卡第15天| 二叉树:翻转二叉树、对称二叉树

相关推荐 python coding with ChatGPT 打卡第12天| 二叉树:理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 文章目录 翻转二叉树Key Points相关题目视频讲解重点分析递归遍历…...

Python(19)Excel表格操作Ⅰ

目录 导包 读取EXCEL文件 1、获取worksheet名称 2、设定当前工作表 3、输出目标单元格数据 4、工作表.rows(行) 5、工作表.columns(列) 小结 导包 要想使用 python 操作 Excel 文件,应当导入 openpyxl 包。在…...

HiveSQL题——聚合函数(sum/count/max/min/avg)

目录 一、窗口函数的知识点 1.1 窗户函数的定义 1.2 窗户函数的语法 1.3 窗口函数分类 聚合函数 排序函数 前后函数 头尾函数 1.4 聚合函数 二、实际案例 2.1 每个用户累积访问次数 0 问题描述 1 数据准备 2 数据分析 3 小结 2.2 各直播间最大的同时在线人数 …...

计算机是什么做的

背景 虽然我是科班出身的,但是上大学时候,对这些内容并不感兴趣,只是简单的进行做题,考试而已。并没有思考,为啥学计算机组成原理,模电数电,微机原理,单片机,操作系统啥…...

C++多线程1(复习向笔记)

创建线程以及相关函数 当用thread类创建线程对象绑定函数后&#xff0c;该线程在主线程执行时就已经自动开始执行了,join起到阻塞主线程的作用 #include <iostream> #include <thread> #include <string> using namespace std; //测试函数 void printStrin…...

代理IP在游戏中的作用有哪些?

游戏代理IP的作用是什么&#xff1f;IP代理软件相当于连接客户端和虚拟服务器的软件“中转站”&#xff0c;在我们向远程服务器提出需求后&#xff0c;代理服务器首先获得用户的请求&#xff0c;然后将服务请求转移到远程服务器&#xff0c;然后将远程服务器反馈的结果转移到客…...

SVN Previous operation has not finished; run ‘cleanup‘ if it was interrupted

SVN cleanup出现下面的提示&#xff1a; svn: E155017: Can’t install ‘*’ from pristine store, because no checksum is recorded for this file svn报错&#xff1a;“Previous operation has not finished; run ‘cleanup’ if it was interrupted“ 解决办法  当遇到…...

MATLAB知识点:MATLAB的文件管理

​讲解视频&#xff1a;可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇&#xff08;数学建模清风主讲&#xff0c;适合零基础同学观看&#xff09;_哔哩哔哩_bilibili 节选自第2章 上一章我们说过&#xff0c;MATLAB是一款非常强…...

【深度学习】MNN ImageProcess处理图像顺序,逻辑,均值,方差

文章目录 介绍Opencv numpy等效的MNN处理 介绍 MNN ImageProcess处理图像是先reisze还是后resize&#xff0c;均值方差怎么处理&#xff0c;是什么通道顺序&#xff1f;这篇文章告诉你答案。 Opencv numpy 这段代码是一个图像预处理函数&#xff0c;用于对输入的图像进行一系…...

代码随想录算法训练营29期Day35|LeetCode 860,406,452

文档讲解&#xff1a;柠檬水找零 根据身高重建队列 用最小数量的箭引爆气球 860.柠檬水找零 题目链接&#xff1a;https://leetcode.cn/problems/lemonade-change/description/ 思路&#xff1a; 很简单&#xff0c;模拟即可。统计五美元、十美元和十五美元的个数。给五美元…...

20240130金融读报1分钟小得01

1、开放银行本质上是以用户需求为核心&#xff0c;以场景服务为切入点的共享平台金融模式&#xff0c;一定程度上加快了商业银行“隐形”和金融服务的无缝和泛在 2、利用自身优势进行差异化竞争&#xff0c;比如农信的客户面对面交流、全方位覆盖、政银紧密合作。针对劣势进行互…...

刷力扣题过程中发现的不熟的函数

C中不熟的函数 1.memset() 头文件&#xff1a;<string.h> void *memset(void *s,int c,unsigned long n); 为指针变量s所指的前n个字节的内存单元填充给定的int型数值c 如&#xff1a; int a[10]; memset(a,0,sizeof(a)); //将数组a中的数全部赋值为02.sort() &#…...

native2ascii命令详解

native2ascii命令详解 大家好&#xff0c;我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01;今天&#xff0c;我们将深入研究一个在Java开发中常用的命令——native2ascii&#xff0c;解析…...

什么是Vue Vue入门案例

一、什么是Vue 概念&#xff1a;Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套 构建用户界面 的 渐进式 框架 Vue2官网&#xff1a;Vue.js 1.什么是构建用户界面 基于数据渲染出用户可以看到的界面 2.什么是渐进式 所谓渐进式就是循序渐进&#xff0c;不一定非得把V…...

【C/Python】GtkApplicationWindow

一、C语言 GtkApplicationWindow 是 GTK 库中用于创建应用程序主窗口的一个控件。 首先&#xff0c;需要确保环境安装了GTK开发库。然后&#xff0c;以下是一个简单的使用 GtkApplicationWindow 创建一个 GTK 应用程序的示例&#xff1a; #include <gtk/gtk.h>static …...

SpringBoot自定义全局事务

1.说明 关于EnableTransactionManagement注解&#xff0c;可加可不加&#xff0c;加注解保证规范性。 2.核心代码 /** * author: wangning * date: 2024/1/23 16:19 */ Aspect Configuration ConditionalOnClass({TransactionManager.class, TransactionFactory.class}) pub…...

【FINEBI】finebi中常用图表类型及其适用场景

柱状图&#xff08;Bar Chart&#xff09;&#xff1a; 比较不同类别或组之间的数量差异&#xff1a;柱状图可以用于比较不同产品、地区、时间段等的销售额、市场份额等。 显示不同时间段的数据变化&#xff1a;通过绘制柱状图&#xff0c;可以观察到销售额、网站流量等随时间…...

Kaggle竞赛系列_SpaceshipTitanic金牌方案分析_数据分析

文章目录 【文章系列】【前言】【比赛简介】【正文】&#xff08;一&#xff09;数据获取&#xff08;二&#xff09;数据分析1. 缺失值2. 重复值3. 属性类型分析4. 类别分析5. 分析目标数值占比 &#xff08;三&#xff09;属性分析1. 对年龄Age分析&#xff08;1&#xff09;…...

Tortoise-tts Better speech synthesis through scaling——TTS论文阅读

笔记地址&#xff1a;https://flowus.cn/share/a79f6286-b48f-42be-8425-2b5d0880c648 【FlowUs 息流】tortoise 论文地址&#xff1a; Better speech synthesis through scaling Abstract: 自回归变换器和DDPM&#xff1a;自回归变换器&#xff08;autoregressive transfo…...

单元测试工具JEST入门——纯函数的测试

单元测试工具JEST入门——纯函数的测试 什么是测试❓&#x1f649; 我只是开发而已&#xff1f;常见单元测试工具 &#x1f527;jest的使用&#x1f440; 首先你得知道一个简单的例子&#x1f330;&#x1f628; Oops&#xff01;出现了一些问题&#x1f44f; 高效的持续监听&a…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...