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

C++力扣题目226--翻转二叉树

给你一棵二叉树的根节点 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 = []
输出:[]

题外话

这道题目是非常经典的题目,也是比较简单的题目(至少一看就会)。

但正是因为这道题太简单,一看就会,一些同学都没有抓住起本质,稀里糊涂的就把这道题目过了。

如果做过这道题的同学也建议认真看完,相信一定有所收获!

#思路

我们之前介绍的都是各种方式遍历二叉树,这次要翻转了,感觉还是有点懵逼。

这得怎么翻转呢?

如果要从整个树来看,翻转还真的挺复杂,整个树以中间分割线进行翻转,如图:

226.翻转二叉树1

可以发现想要翻转它,其实就把每一个节点的左右孩子交换一下就可以了。

关键在于遍历顺序,前中后序应该选哪一种遍历顺序? (一些同学这道题都过了,但是不知道自己用的是什么顺序)

遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。

注意只要把每一个节点的左右孩子翻转一下,就可以达到整体翻转的效果

这道题目使用前序遍历和后序遍历都可以,唯独中序遍历不方便,因为中序遍历会把某些节点的左右孩子翻转了两次!建议拿纸画一画,就理解了

那么层序遍历可以不可以呢?依然可以的!只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的!

#递归法

对于二叉树的递归法的前中后序遍历,已经在二叉树:前中后序递归遍历 (opens new window)详细讲解了。

我们下文以前序遍历为例,通过动画来看一下翻转的过程:

翻转二叉树

我们来看一下递归三部曲:

  1. 确定递归函数的参数和返回值

参数就是要传入节点的指针,不需要其他参数了,通常此时定下来主要参数,如果在写递归的逻辑中发现还需要其他参数的时候,随时补充。

返回值的话其实也不需要,但是题目中给出的要返回root节点的指针,可以直接使用题目定义好的函数,所以就函数的返回类型为TreeNode*

TreeNode* invertTree(TreeNode* root)
  1. 确定终止条件

当前节点为空的时候,就返回

if (root == NULL) return root;

  1. 确定单层递归的逻辑

因为是先前序遍历,所以先进行交换左右孩子节点,然后反转左子树,反转右子树。

swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);

基于这递归三步法,代码基本写完,C++代码如下:

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;swap(root->left, root->right);  // 中invertTree(root->left);         // 左invertTree(root->right);        // 右return root;}
};

#迭代法

#深度优先遍历

二叉树:听说递归能做的,栈也能做! (opens new window)中给出了前中后序迭代方式的写法,所以本题可以很轻松的写出如下迭代法的代码:

C++代码迭代法(前序遍历)

class Solution {
public:TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;stack<TreeNode*> st;st.push(root);while(!st.empty()) {TreeNode* node = st.top();              // 中st.pop();swap(node->left, node->right);if(node->right) st.push(node->right);   // 右if(node->left) st.push(node->left);     // 左}return root;}
};

如果这个代码看不懂的话可以再回顾一下二叉树:听说递归能做的,栈也能做! (opens new window)。

我们在二叉树:前中后序迭代方式的统一写法 (opens new window)中介绍了统一的写法,所以,本题也只需将文中的代码少做修改便可。

C++代码如下迭代法(前序遍历)

class Solution {
public:TreeNode* invertTree(TreeNode* root) {stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();if (node->right) st.push(node->right);  // 右if (node->left) st.push(node->left);    // 左st.push(node);                          // 中st.push(NULL);} else {st.pop();node = st.top();st.pop();swap(node->left, node->right);          // 节点处理逻辑}}return root;}
};

如果上面这个代码看不懂,回顾一下文章二叉树:前中后序迭代方式的统一写法 (opens new window)。

#广度优先遍历

也就是层序遍历,层数遍历也是可以翻转这棵树的,因为层序遍历也可以把每个节点的左右孩子都翻转一遍,代码如下:

class Solution {
public:TreeNode* invertTree(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();swap(node->left, node->right); // 节点处理if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return root;}
};

如果对以上代码不理解,或者不清楚二叉树的层序遍历,可以看这篇二叉树:层序遍历登场!(opens new window)

#拓展

文中我指的是递归的中序遍历是不行的,因为使用递归的中序遍历,某些节点的左右孩子会翻转两次。

如果非要使用递归中序的方式写,也可以,如下代码就可以避免节点左右孩子翻转两次的情况:

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:TreeNode* invertTree(TreeNode* root) {stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();if (node->right) st.push(node->right);  // 右st.push(node);                          // 中st.push(NULL);if (node->left) st.push(node->left);    // 左} else {st.pop();node = st.top();st.pop();swap(node->left, node->right);          // 节点处理逻辑}}return root;}
};

为什么这个中序就是可以的呢,因为这是用栈来遍历,而不是靠指针来遍历,避免了递归法中翻转了两次的情况,大家可以画图理解一下,这里有点意思的。

#总结

针对二叉树的问题,解题之前一定要想清楚究竟是前中后序遍历,还是层序遍历。

二叉树解题的大忌就是自己稀里糊涂的过了(因为这道题相对简单),但是也不知道自己是怎么遍历的。

这也是造成了二叉树的题目“一看就会,一写就废”的原因。

针对翻转二叉树,我给出了一种递归,三种迭代(两种模拟深度优先遍历,一种层序遍历)的写法,都是之前我们讲过的写法,融汇贯通一下而已。

大家一定也有自己的解法,但一定要成方法论,这样才能通用,才能举一反三!

相关文章:

C++力扣题目226--翻转二叉树

给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1]示例 2&#xff1a; 输入&#xff1a;root [2,1,3] 输出&#xff1a;[2,3,1]示例 3&#x…...

Gorm 数据库表迁移与表模型定义

文章目录 一、Docker快速创建MySQL实例1.1 创建1.3 创建数据库 二、AutoMigrate介绍与使用2.1 AutoMigrate介绍2.2 AutoMigrate 基本使用 三、模型定义3.1 模型定义3.2 快速增删改查3.3 约定3.4 gorm.Model 四、表模型主键、表名、列名的约定4.1 主键&#xff08;Primary Key&a…...

系列三、Spring Security中自定义用户名/密码

一、Spring Security中自定义用户名/密码 1.1、自定义用户名/密码 1.1.1、配置文件中配置 spring.security.user.nameroot spring.security.user.password123456 1.1.2、定义基于内存的用户 /*** Author : 一叶浮萍归大海* Date: 2024/1/11 21:50* Description:*/ Configu…...

如何顺滑使用华为云编译构建平台?

这两年平台构建服务需求越来越大&#xff0c;却一直苦于找不到一些指南&#xff0c; 这里特意写了一篇&#xff0c; 对在学习代码阶段和新手程序员朋友也蛮友好&#xff0c; 配置真的也不难&#xff0c; 也特别适合想尝试从0到1做个APP的朋友了。 以华为云的CodeArts Build为例…...

查看Linux磁盘空间

(1)、该命令会列出当前系统所有挂载的文件系统以及它们的使用情况&#xff0c;包括总容量、已用空间、可用空间、使用百分比等信息 df -h如果查看某一个文件夹的,可以 df -h folderName (2)、计算指定目录下所有文件和子目录所占用的磁盘空间大小&#xff0c;并以人类可读的格…...

2023年全国职业院校技能大赛(高职组)“云计算应用”赛项赛卷⑩

2023年全国职业院校技能大赛&#xff08;高职组&#xff09; “云计算应用”赛项赛卷10 目录 需要竞赛软件包环境以及备赛资源可私信博主&#xff01;&#xff01;&#xff01; 2023年全国职业院校技能大赛&#xff08;高职组&#xff09; “云计算应用”赛项赛卷10 模块…...

vim基本操作命令

一、vi简介 vi是“Visual interface”的简称&#xff0c;它在Linux上的地位就仿佛Edit程序在DOS上一样。它可以执行输出、删除、查找、替换、块操作等众多文本操作&#xff0c;而且用户可以根据自己的需要对其进行定制。Vi不是一个排版程序&#xff0c;它不象Word或WPS那样可以…...

mybatis-plus实现真正的批量插入

1、安装依赖 <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-extension</artifactId><version>3.5.3.2</version></dependency>版本与mybatis-plus一致 2、编写sql注入器 package com.example.answe…...

pytorch12:GPU加速模型训练

目录 1、CPU与GPU2、数据迁移至GPU2.1 to函数使用方法 3、torch.cuda常用方法4、多GPU并行运算4.1 torch.nn.DataParallel4.2 torch.distributed加速并行训练 5、gpu总结 1、CPU与GPU CPU&#xff08;Central Processing Unit, 中央处理器&#xff09;&#xff1a;主要包括控制…...

P1603 斯诺登的密码题解

题目 &#xff08;1&#xff09;找出句子中所有用英文表示的数字(≤20)&#xff0c;列举在下&#xff1a; 正规&#xff1a;one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen twenty 非正规…...

YOLOv8 + openVINO 多线程数据读写顺序处理

多线程数据读写顺序处理 一个典型的生产者-消费者模型&#xff0c;在这个模型中&#xff0c;多个工作线程并行处理从共享队列中获取的数据&#xff0c;并将处理结果以保持原始顺序的方式放入另一个队列。 多线程处理模型&#xff0c;具体细节如下&#xff1a; 1.数据:数据里必…...

端到端自动驾驶

自动驾驶主要流程&#xff1a;感知->预测->规划 预测是预测周围目标&#xff08;车、行人、动物等&#xff09;的轨迹&#xff0c;规划是规划自车的运动轨迹。 UniAD[CVPR 2023]: 使用transformer架构&#xff0c;统一自动驾驶流程&#xff0c;完成所有检测&#xff0c…...

Developer Tools for Game Creator 1

插件包含: 持久世界时间管理系统 单击以生成对象或预设 游戏内调试控制台 游戏内事件控制台 控制台管理控制 命令模板脚本 游戏内屏幕截图 低分辨率和高分辨率图像 缩略图生成 移动支持 使用Game Creator Action或拖放来激活和控制组件,无需编码。 通过此资产,您可以获得: …...

软件测试|好用的pycharm插件推荐(三)——Rainbow Brackets

简介 我们平时写代码的时候&#xff0c;括号是让我们非常头疼的地方&#xff0c;特别是代码逻辑很多&#xff0c;层层嵌套的情况。 一眼很难看出&#xff0c;代码是从哪个括号开始&#xff0c;到哪个反括号结束的。这个时候要是有一款工具能够让我们一眼就看出代码从哪个括号开…...

MyBatisPlus学习二:常用注解、条件构造器、自定义sql

常用注解 基本约定 MybatisPlus通过扫描实体类&#xff0c;并基于反射获取实体类信息作为数据库表信息。可以理解为在继承BaseMapper 要指定对应的泛型 public interface UserMapper extends BaseMapper<User> 实体类中&#xff0c;类名驼峰转下划线作为表名、名为id的…...

深入理解C#中的引用类型、引用赋值以及 `ref` 关键字

深入理解C#中的引用类型、引用赋值以及 ref 关键字 在C#编程中&#xff0c;理解引用类型、引用赋值以及 ref 关键字的使用对于编写高效、可靠的代码至关重要。本文将深入探讨这些概念&#xff0c;帮助您更好地理解C#的工作原理。 引用类型简介 在C#中&#xff0c;所有的类型都…...

【算法提升】LeetCode每五日一总结【01/01--01/05】

文章目录 LeetCode每五日一总结【01/01--01/05】2023/12/31今日数据结构&#xff1a;二叉树的前/中/后 序遍历<非递归> 2024/01/01今日数据结构&#xff1a;二叉树的 前/中/后 序遍历 三合一代码<非递归>今日数据结构&#xff1a;二叉树的 前/中/后 序遍历 三合一代…...

linux下驱动学习—平台总线 (3)

platform 设备驱动 在设备驱动模型中&#xff0c; 引入总线的概念可以对驱动代码和设备信息进行分离。但是驱动中总线的概念是软件层面的一种抽象&#xff0c;与我们SOC中物理总线的概念并不严格相等&#xff1a; 物理总线&#xff1a;芯片与各个功能外设之间传送信息的公共通…...

【leetcode】字符串中的第一个唯一字符

题目描述 给定一个字符串 s &#xff0c;找到 它的第一个不重复的字符&#xff0c;并返回它的索引 。如果不存在&#xff0c;则返回 -1 。 用例 示例 1&#xff1a; 输入: s “leetcode” 输出: 0 示例 2: 输入: s “loveleetcode” 输出: 2 示例 3: 输入: s “aabb”…...

Serverless与Kubernetes(K8s)的区别、优缺点及应用场景

Serverless与Kubernetes&#xff08;K8s&#xff09;的区别 架构模型 Serverless是一种基于事件驱动的计算模型&#xff0c;它允许开发者编写应用程序时无需关心底层的基础设施。在Serverless架构中&#xff0c;云服务提供商会负责管理服务器、操作系统、运行时环境等基础设施&…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...