LeetCode 热题100 226. 翻转二叉树
LeetCode 热题100 | 226. 翻转二叉树
大家好,今天我们来解决一道经典的算法题——翻转二叉树。这道题在 LeetCode 上被标记为简单难度,要求我们翻转一棵二叉树,并返回其根节点。下面我将详细讲解解题思路,并附上 Python 代码实现。
题目描述
给定一棵二叉树的根节点 root,翻转这棵二叉树,并返回其根节点。
示例:
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
解题思路
翻转二叉树的核心思想是交换每个节点的左右子树。我们可以通过递归或迭代的方式来实现。
核心思想
-
递归法:
- 递归地翻转左子树和右子树。
- 交换当前节点的左右子树。
-
迭代法(BFS):
- 使用队列进行层次遍历,逐层交换每个节点的左右子树。
代码实现
方法 1:递归法
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef invertTree(root):""":type root: TreeNode:rtype: TreeNode"""if not root:return None# 递归翻转左右子树left = invertTree(root.left)right = invertTree(root.right)# 交换当前节点的左右子树root.left = rightroot.right = leftreturn root
方法 2:迭代法(BFS)
from collections import dequedef invertTree(root):""":type root: TreeNode:rtype: TreeNode"""if not root:return Nonequeue = deque([root]) # 使用队列存储节点while queue:node = queue.popleft() # 弹出当前节点# 交换当前节点的左右子树node.left, node.right = node.right, node.left# 将左右子节点加入队列if node.left:queue.append(node.left)if node.right:queue.append(node.right)return root
代码解析
递归法
-
递归终止条件:
- 如果当前节点为空,返回
None。
- 如果当前节点为空,返回
-
递归翻转左右子树:
- 递归地翻转左子树和右子树。
-
交换当前节点的左右子树:
- 将当前节点的左子树指向翻转后的右子树,右子树指向翻转后的左子树。
-
返回根节点:
- 返回翻转后的二叉树的根节点。
迭代法(BFS)
-
初始化:
- 如果根节点为空,直接返回
None。 - 使用队列存储节点,初始时将根节点加入队列。
- 如果根节点为空,直接返回
-
遍历队列:
- 弹出当前节点,交换其左右子树。
- 将当前节点的左右子节点加入队列。
-
返回根节点:
- 遍历结束后,返回翻转后的二叉树的根节点。
复杂度分析
- 时间复杂度:O(n),其中 n 是二叉树的节点数。每个节点被访问一次。
- 空间复杂度:
- 递归法:O(h),其中 h 是二叉树的高度,递归调用栈的深度为树的高度。
- 迭代法:O(n),队列的最大空间为树的宽度。
示例运行
示例 1
# 创建二叉树 [4,2,7,1,3,6,9]
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)# 翻转二叉树
inverted_root = invertTree(root)# 层序遍历输出结果
def levelOrder(root):if not root:return []result = []queue = deque([root])while queue:level_size = len(queue)level_nodes = []for _ in range(level_size):node = queue.popleft()level_nodes.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)result.append(level_nodes)return resultprint(levelOrder(inverted_root)) # 输出: [[4], [7, 2], [9, 6, 3, 1]]
示例 2
# 创建二叉树 [2,1,3]
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)# 翻转二叉树
inverted_root = invertTree(root)# 层序遍历输出结果
print(levelOrder(inverted_root)) # 输出: [[2], [3, 1]]
示例 3
# 创建空二叉树 []
root = None# 翻转二叉树
inverted_root = invertTree(root)# 层序遍历输出结果
print(levelOrder(inverted_root)) # 输出: []
总结
通过递归或迭代的方式,我们可以高效地翻转二叉树。递归法代码简洁,但可能受递归深度限制;迭代法使用队列进行层次遍历,适合处理较大的树。希望这篇题解对你有帮助!如果还有其他问题,欢迎继续提问!
关注我,获取更多算法题解和编程技巧!
相关文章:
LeetCode 热题100 226. 翻转二叉树
LeetCode 热题100 | 226. 翻转二叉树 大家好,今天我们来解决一道经典的算法题——翻转二叉树。这道题在 LeetCode 上被标记为简单难度,要求我们翻转一棵二叉树,并返回其根节点。下面我将详细讲解解题思路,并附上 Python 代码实现…...
mysql 拼接多行合并为一行
如图所示,在variety相同的前提下拼接rating为ratingList,year_term为yearTermList sql如下: SELECT variety,GROUP_CONCAT(rating ORDER BY rating SEPARATOR ,) AS ratingList,GROUP_CONCAT(year_term ORDER BY year_term SEPARATOR…...
【Java项目】基于Spring Boot的论坛管理系统
【Java项目】基于Spring Boot的论坛管理系统 技术简介:采用Java技术、Spring Boot框架、MySQL数据库等实现。 系统简介:论坛管理系统是一个基于Web的在线平台,主要分为前台和后台两大功能模块。前台功能模块包括(1)首…...
unity学习54:图片+精灵+遮罩mask,旧版文本 text 和新的TMP文本
目录 1 图片 image 1.1 如果直接导入image 1.2 图片 image 和精灵 sprite 1.2.1 继续修改上面的格式 texture type 是default 1.2.2 再次关联到UI的 image 物体上就可以了 1.3 图片和遮罩 mask 1.3.1 创建1个父物体和1个子物体,分别都是image 1.3.2 如果父…...
2024年国赛高教杯数学建模D题反潜航空深弹命中概率问题解题全过程文档及程序
2024年国赛高教杯数学建模 D题 反潜航空深弹命中概率问题 原题再现 应用深水炸弹(简称深弹)反潜,曾是二战时期反潜的重要手段,而随着现代军事技术的发展,鱼雷已成为现代反潜作战的主要武器。但是,在海峡或…...
什么是数字人
什么是数字人 Ultralight-Digital-Human 是一个能在移动设备上实时运行的数字人模型仓库,可能是第一个开源的如此轻量级的数字人模型。 主要特点 轻量级:能够在移动设备上实时运行。开源:代码和模型公开,方便开发者使用和改进。文件结构 根目录: README.md:项目的说明文…...
15.5 基于 RetrievalQA 的销售话术增强系统实战:构建智能销售大脑
基于 RetrievalQA 的销售话术增强系统实战:构建智能销售大脑 关键词:RetrievalQA 应用实战、销售知识增强、语义检索优化、上下文感知问答、多源知识融合 1. RetrievalQA 技术原理与销售场景适配 1.1 RetrievalQA 核心工作机制 #mermaid-svg-VL2yIusgl4oprXUr {font-family…...
软件供应链安全工具链研究系列—RASP自适应威胁免疫平台(下篇)
在“软件供应链安全工具链研究系列—RASP自适应威胁免疫平台-上篇”中我们提到了RASP工具的基本能力、原理以及工具的应用场景,了解到了RASP工具在各场景下发挥的价值。那么在当今高强度攻防对抗的大场景下,RASP作为最后一道防线,不论是从高危…...
WordPress网站502错误全面排查与解决指南
502 Bad Gateway错误是WordPress站长最常遇到的服务器问题之一,它意味着服务器作为网关或代理时,未能从上游服务器获取有效响应。针对WP可能出现的502问题,本文提供一些基础到进阶的解决方案供大家参考:) 一、502错误的本质和核心诱因 502错误属于HTTP状态码中的5xx系列,…...
PCL源码分析:曲面法向量采样
文章目录 一、简介二、源码分析三、实现效果参考资料一、简介 曲面法向量点云采样,整个过程如下所述: 1、空间划分:使用递归方法将点云划分为更小的区域, 每次划分选择一个维度(X、Y 或 Z),将点云分为两部分,直到划分区域内的点少于我们指定的数量,开始进行区域随机采…...
HTTP 动态报错码的原因和解决方法
目录 1xx(信息性状态码) 2xx(成功状态码) 3xx(重定向状态码) 4xx(客户端错误状态码) 5xx(服务器错误状态码) 参考文章 以下是 HTTP 动态报错码的常见原…...
1分钟用DeepSeek编写一个PDF转Word软件
一、引言 如今,在线工具的普及让PDF转Word成为了一个常见需求,常见的pdf转word工具有收费的wps,免费的有pdfgear,见下文: PDFgear:一款免费的PDF编辑、格式转化软件-CSDN博客 还有网上在线的免费pdf转word工具smallp…...
生成对抗网络(GAN)
生成对抗网络(GAN):生成对抗网络是一种深度学习模型,由 Ian Goodfellow 等人在 2014 年提出。GAN由生成器和判别器组成,生成器生成假数据,判别器区分真假数据。两者通过对抗训练不断提升,最终生成器能够生成…...
openlayers结合turf geojson面获取面积和中心点
在 OpenLayers 中绘制 GeoJSON 面要素并计算面积和中心点,可以结合 OpenLayers 的 ol/format/GeoJSON 模块将 GeoJSON 数据转换为 OpenLayers 的 Feature,然后使用 Turf.js 进行计算。示例代码如下 import Map from ol/Map; import View from ol/View; …...
【SRC实战】修改金币数量实现财富自由
01 — 漏洞证明 1、进入阅读奖励 2、此时金币数量0 3、来到新手福利处 4、观看广告获取奖励 5、由于int整型范围-2147483648~2147483647,避免溢出,此处修改请求包中coinNum参数为2147483640 6、返回查看金币数量变为2147483640 02 — 漏洞…...
地理数据可视化:飞线说明(笔记)
//主要代码 //黄色飞线s_data.push({type: lines,zlevel: 2,effect: {//线上的箭头效果show: true,period: 1.5,//控制点的流动速度,数越小流动的速度越快trailLength: 0.1,//动画的拖尾时长// color: #2ef358,color: #ffeb40,symbol: planePath,//控…...
2024最新版鸿蒙纯血原生应用开发教程文档丨学习ArkTS语言-基本语法
ArkTS是HarmonyOS的主要应用开发语言,在TypeScript基础上进行了扩展,保留了其基本风格,并通过增强静态检查和分析来提高程序的稳定性和性能。本教程将帮助开发者掌握ArkTS的核心功能、语法及最佳实践,以便高效地构建高性能移动应用…...
微信小程序-二维码绘制
wxml <view bindlongtap"saveQrcode"><!-- 二维码 --><view style"position: absolute;background-color: #FFFAEC;width: 100%;height: 100vh;"><canvas canvas-id"myQrcode" style"width: 200px; height: 200px;ba…...
轻量化网络设计|ShuffleNet:深度学习中的轻量化革命
一、引言 在深度学习中,卷积神经网络(Convolutional Neural Networks,CNN)无疑是大家最耳熟能详的算法之一。自诞生以来,CNN 在图像分类、目标检测、语义分割等众多计算机视觉任务中取得了令人瞩目的成就,…...
一天记20个忘10个之五:land
一天记20个忘10个之五:land land n.陆地,土地 v.着陆,降落 // la-拉、宽广 nd后缀 字面义:宽广的土地 陆地 landing n.着陆,降落lander n.登陆车,着陆者 派生: island岛,岛屿 //isle(n.用于…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
