当前位置: 首页 > 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…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...