算法练习第15天|226.翻转二叉树
226.翻转二叉树
力扣链接
https://leetcode.cn/problems/invert-binary-tree/description/
题目描述:
给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。
示例 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 = [] 输出:[]
思路分析:
翻转二叉树,其实就把每一个节点的左右孩子交换一下就可以了。注意,是每一个节点的左右子节点。这就可以用到前面所将的二叉树递归遍历和层序遍历。下面分别使用前序递归,后序递归和层序遍历来实现。
前序递归实现:
先回顾一下递归三部曲:
1. 确定递归函数参数及返回值
2. 确定递归终止条件
3. 确定单层递归的逻辑操作有哪些
首先,对于函数参数,由于要遍历二叉树,所以要有一个TreeNode*指针来接收根节点,由于不需要对元素提取或其他操作,所以不再需要其他参数。其次,由于题目要求返回翻转后的根节点,所以返回值类型为TreeNode*。
TreeNode* invertTree(TreeNode* root)
第二,递归何时终止?当遇到要遍历的节点的指针为nullptr时,遍历终止。这里的root不仅表示根节点,还可以表示遍历过程中左右子树对应的根节点。
if (root == NULL) return root;
第三,单层递归要做哪些操作?前序遍历首先就要交换左右子节点,然后递归调用本函数分别对左右子树进行同样的操作,然后返回root。
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
整体代码如下:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public://递归前序遍历第一步:确定递归函数参数以及返回值TreeNode* invertTree(TreeNode* root) {//第二步:确定递归终止条件。当前节点指针为空,递归结束if(root == nullptr) return root;//第三步:确认单层递归的逻辑//前序遍历swap(root->left, root->right); //中,交换invertTree(root->left); //左,递归invertTree(root->right); //右,递归return root;}
};
后序递归实现:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public://递归后序遍历第一步:确定递归函数参数以及返回值TreeNode* invertTree(TreeNode* root) {//第二步:确定递归终止条件。当前节点指针为空,递归结束if(root == nullptr) return root;//第三步:确认单层递归的逻辑//后序遍历 invertTree(root->left); //左,递归invertTree(root->right); //右,递归swap(root->left, root->right); //中,交换return root;}
};
中序递归实现:需要注意左中右的右对应的指针
class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;invertTree(root->left); // 左swap(root->left, root->right); // 中invertTree(root->left); // 注意 这里依然要遍历左孩子,因为中间节点已经翻转了return root;}
};
层序遍历实现:
class Solution {
public://层序遍历需要借助队列queueTreeNode* invertTree(TreeNode* root) {queue<TreeNode *> que;if(root != nullptr) que.push(root);elsereturn root;while(!que.empty()){int size = que.size();for(int i =0; i<size; i++){TreeNode * node = que.front();//注意,先交换,再入队左右子节点。否则会先遍历右节点 swap(node->left, node->right);if(node->left) que.push(node->left);if(node->right) que.push(node->right); que.pop();}}return root;}
};
本人在写代码的时候,曾经多给交换前加了个条件,即
//注意,先交换,再入队左右子节点。否则会先遍历右节点
if(node->left!=nullptr && node->right != nullptr)swap(node->left, node->right);
想的是当前节点的左右节点均存在时才进行交换,但是程序未通过:

错误原因是,程序要实现的代码时即使左右子节点未能同时存在,也能完成交换(和nullptr)交换。如下图所示:
所以这个加上的前提条件是不正确的,因此需要删除。
相关文章:
算法练习第15天|226.翻转二叉树
226.翻转二叉树 力扣链接https://leetcode.cn/problems/invert-binary-tree/description/ 题目描述: 给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。 示例 1: 输入:root [4,2,7,1,3,6,9] 输出&am…...
C#面向对象——封装、封装案例示例
C#面向对象——封装 什么是封装? (1)封装是将数据和操作数据的方法(行为)封装在一起。 (2)程序中封装的体现:属性,方法,类,接口,命名空间&#…...
【InternLM 实战营第二期-笔记3】茴香豆:搭建你的 RAG 智能助理
书生浦语是上海人工智能实验室和商汤科技联合研发的一款大模型,很高兴能参与本次第二期训练营,我也将会通过笔记博客的方式记录学习的过程与遇到的问题,并为代码添加注释,希望可以帮助到你们。 记得点赞哟(๑ゝω╹๑) 茴香豆:搭建…...
Advanced RAG 03:运用 RAGAs 与 LlamaIndex 评估 RAG 应用
编者按:目前,检索增强生成(Retrieval Augmented Generation,RAG)技术已经广泛使用于各种大模型应用场景。然而,如何准确评估 RAG 系统的性能和效果,一直是业界和学界共同关注的重点问题。若无法…...
leetcode
找到字符串中所有字母异位词 给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串(包括相同的字符串) 示例 1: 输入: s "…...
Unity DOTS《群体战斗弹幕游戏》核心技术分析之3D角色动画
最近DOTS发布了正式的版本, 我们来分享现在流行基于群体战斗的弹幕类游戏,实现的核心原理。今天给大家介绍大规模战斗群体3D角色的动画如何来实现。 DOTS 对角色动画支持的局限性 截止到Unity DOTS发布的版本1.0.16,目前还是无法很好的支持3D角色动画。在DOTS 的ba…...
react异步组件如何定义使用 标准使用方法
目录 默认导出和命名导出的格式 默认导出的组件 使用方式 命名导出的组件 使用方式 默认导出和命名导出的格式 默认导出: // person.js const person {name: Alice,age: 30 };export default person;命名导出: // math.js export const add (a, b) > a b; exp…...
React + Ts + Vite + Antd 项目搭建
1、创建项目 npm create vite 项目名称 选择 react 选择 typescript 关闭严格模式 建议关闭严格模式,因为不能自动检测副作用,有意双重调用。将严格模式注释即可。 2、配置sass npm install sass 更换所有后缀css为sass vite.config.ts中注册全局样式 /…...
js爬虫puppeteer库 解决网页动态渲染无法爬取
我们爬取这个网址上面的股票实时部分宇通客车(600066)_股票价格_行情_走势图—东方财富网 我们用正常的方法爬取会发现爬取不下来,是因为这个网页这里是实时渲染的,我们直接通过网址接口访问这里还没有渲染出来 于是我们可以通过下面的代码来进行爬取: …...
代码随想录:二叉树5
目录 102.二叉树的层序遍历 题目 代码(队列实现) 107.二叉树的层序遍历II 题目 代码 199.二叉树的右视图 题目 代码 637.二叉树的层平均值 题目 代码 102.二叉树的层序遍历 题目 给你二叉树的根节点 root ,返回其节点值的 层序遍…...
Tomcat 获取客户端真实IP X-Forwarded-For
Tomcat 获取客户端真实IP X-Forwarded-For 代码实现: 在Host标签下面添加代码: <Valve className"org.apache.catalina.valves.RemoteIpValve" remoteIpHeader"x-forwarded-for" remoteIpProxiesHeader"x-forwarded-by&q…...
记录PS学习查漏补缺
PS学习 PS学习理论快捷键抠图PS专属多软件通用快捷键 PS学习 理论 JPEG (不带透明通道) PNG (带透明通道) 快捷键 抠图 抠图方式 魔棒工具 反选选中区域 CtrlShiftI(反选) 钢笔抠图注意事项 按着Ctrl单击节点 会出现当前节…...
Kafka 架构深入探索
目录 一、Kafka 工作流程及文件存储机制 二、数据可靠性保证 三 、数据一致性问题 3.1follower 故障 3.2leader 故障 四、ack 应答机制 五、部署FilebeatKafkaELK 5.1环境准备 5.2部署ELK 5.2.1部署 Elasticsearch 软件 5.2.1.1修改elasticsearch主配置文件 5.2…...
k-means聚类算法的MATLAB实现及可视化
K-means算法是一种无监督学习算法,主要用于数据聚类。其工作原理基于迭代优化,将数据点划分为K个集群,使得每个数据点都属于最近的集群,并且每个集群的中心(质心)是所有属于该集群的数据点的平均值。以下是…...
Excel文件转Asc文件
单个转换 import os import pandas as pdfilename (10)result01-1.xlsx df pd.read_excel(filename) # 读取Excel文件# 将数据保存为ASC格式 asc_filename os.path.splitext(filename)[0] .asc # 获取文件名并替换扩展名 with open(asc_filename, w) as file:# 写入文件…...
【题目】【信息安全管理与评估】2022年国赛高职组“信息安全管理与评估”赛项样题7
【题目】【信息安全管理与评估】2022年国赛高职组“信息安全管理与评估”赛项样题7 信息安全管理与评估 网络系统管理 网络搭建与应用 云计算 软件测试 移动应用开发 任务书,赛题,解析等资料,知识点培训服务 添加博主wx:liuliu548…...
Webrtc 信令服务器实现
webrtc建联流程图 由上图可知,所谓的信令服务器其实就是将peer的offer/candidate/answer传给对端而已。这样的话实现方式就有很多种了,目前普遍的方式HTTP/HTTPS,WS/WSS。像webrtc-demo-peerconnection就是实现HTTP这种方式。本文使用WS&…...
【Blockchain】连接智能合约与现实世界的桥梁Chainlink
去中心化预言机试图实现依赖因果关系而不是个人关系的去信任和确定性结果。它以与区块链网络相同的方式实现这些结果,即在许多网络参与者之间分配信任。通过利用许多不同的数据源并实施不受单个实体控制的预言机系统,去中心化的预言机网络有可能为智能合…...
解决EasyPoi导入Excel获取不到第一列的问题
文章目录 1. 复现错误2. 分析错误2.1 导入的代码2.2 DictExcel实体类2.2 表头和标题3. 解决问题1. 复现错误 使用EasyPoi导入数据时,Excel表格如下图: 但在导入时,出现如下错误: name为英文名称,在第一列,Excel表格有值,但导入的代码中为null,就很奇怪? 2. 分析错误 …...
Vue 阶段练习:记事本
将 Vue快速入门 和 Vue 指令的学习成果应用到实际场景中(如该练习 记事本),我们能够解决实际问题并提升对 Vue 的技能掌握。 目录 功能展示 需求分析 我的代码 案例代码 知识点总结 功能展示 需求分析 列表渲染删除功能添加功能底部统计…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
