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

翻转二叉树

声明

该系列文章仅仅展示个人的解题思路和分析过程,并非一定是优质题解,重要的是通过分析和解决问题能让我们逐渐熟练和成长,从新手到大佬离不开一个磨练的过程,加油!

原题链接

翻转二叉树备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/invert-binary-tree/

算法分析

        如下图1和图2可按照(1)、(2)、(3)、(4)的顺序依次对每个非叶子节点的左右孩子节点进行镜像反转,对于只有一个孩子节点的节点也要进行镜像反转操作。

图1

图2

        分析:

        1.如何完成镜像反转?

        可以通过递归遍历整棵树,遍历过程中按照以下方式进行判断和操作:

        (1)若当前节点为空或无左孩子和右孩子节点则return;

        (2)否则继续遍历左右孩子节点;

        (3)交换左右孩子节点;

        2.如何交换左右孩子节点?

        (1)左右孩子节点均不为空,则交换左右孩子节点;

        (2)左孩子节点为空&&右孩子节点不为空,则左孩子节点=右孩子节点,右孩子节点置空;

        (3)右孩子节点为空&&左孩子节点不为空,则右孩子节点=左孩子节点,左孩子节点置空.

代码示例(C#)
//翻转二叉树
public TreeNode MirrorTree(TreeNode root)
{if (root != null) Reverse(root);return root;
}//对以指定节点为根节点的二叉树进行镜像反转操作
private void Reverse(TreeNode node)
{//检测是否满足镜像反转要求if (node == null || (node.left == null && node.right == null)) return;if (node.left != null) Reverse(node.left);//对当前节点的左孩子节点进行镜像反转操作if (node.right != null) Reverse(node.right);//对当前节点的右孩子节点进行镜像反转操作SwapChildren(node);//交换当前节点的左右孩子节点
}//交换指定节点的左右孩子节点
private void SwapChildren(TreeNode node)
{if (node.left != null && node.right != null)(node.left, node.right) = (node.right, node.left);else if (node.left == null && node.right != null)(node.left, node.right) = (node.right, null);else if (node.left != null && node.right == null)(node.right, node.left) = (node.left, null);
}
算法解说

       根据题目要求我们需要对一个二叉树进行翻转操作,主方法的输入是该二叉树的根节点,返回值也是一个节点。实际上我们可以对问题进行细分,对二叉树的翻转实际上就是对二叉树节点的交换或者说是将每个节点的位置进行重新排序,有的节点的位置保持不变(如根节点),有的节点则需要与其它节点交换位置(如叶子节点等)。

       对问题进行转换后,我们自然需要对整个二叉树进行遍历,那么我们就需要搞清楚两个问题。

       1.什么时候交换节点?

       2.怎么交换节点?

       如图1和图2我们列举出了本题目将会出现的两种二叉树,根据这两种二叉树我们去找到上面两个问题的答案,具体思路请参考算法分析。

       如何将算法分析转换为代码,依旧是确定两个点,一是变量,二是逻辑主体,本题目的算法分析中并没有要求需要单独定义变量去记录数据,所以我们只看逻辑主体即可,代码示范中,我们将节点交换方法独立出来,以方便维护以及增加可读性,由于我们采用的是递归方式遍历二叉树,所以进行二叉树反转的逻辑我们也将其单独定义为一个函数。

相关文章:

翻转二叉树

声明 该系列文章仅仅展示个人的解题思路和分析过程,并非一定是优质题解,重要的是通过分析和解决问题能让我们逐渐熟练和成长,从新手到大佬离不开一个磨练的过程,加油! 原题链接 翻转二叉树备战技术面试?…...

检测新突破 | AlignDet:支持各类检测器自监督新框架(ICCV2023)

引言 论文链接:https://arxiv.org/abs/2307.11077 项目地址:https://github.com/liming-ai/AlignDet 这篇论文主要研究目标检测领域的自监督预训练方法。作者首先指出,当前主流的预训练-微调框架在预训练和微调阶段存在数据、模型和任务上的…...

03.Show and Tell

目录 前言泛读摘要IntroductionRelated Work小结 精读模型基于LSTM的句子生成器TrainingInference 实验评价标准数据集训练细节分数结果生成结果多样性讨论排名结果人工评价结果表征分析 结论 代码 前言 本课程来自深度之眼《多模态》训练营,部分截图来自课程视频。…...

QStackedWidget 的使用

QStackedWidget QStackedWidget 提供一些层叠的 Widget,同一时间只有一个Widget处于可视状态,就像书本一样。 什么时候使用 QStackedWidget 强烈建议 如果需要点击一个按钮显示一些界面再点击按钮隐藏当前界面而去显示另外的界面时。都使用 QStackedW…...

大数据--难点--地图的制作

地图一直是亮点也是难点,刚刚进公司的时候也很难懂~~做出来的也很难看 纯CSS3使用vw和vh视口单位实现h5页面自适应,gulp自动监听sass改动并保存到css中 当修改了sass里面的代码后,gulp会自动监听修改内容并同名保存到css文件夹中&#xff0…...

【AI作画】使用Stable Diffusion的艺术二维码完全生成攻略

文章目录 前言Stable Diffusion 简介 什么是云端平台?优势灵活性和可扩展性成本效益高可用性和容错性管理简便性 选择适合的云端平台 平台优势平台操作购买算力并创建工作空间启动工作空间应用市场一键安装 使用Stable-Diffusion作图使用控制网络将文本转图像二维码…...

SQLAlchemy------更多查询

1 查询: filer:写条件 filter_by:等于的值 res session.query(User).all() # 是个普通列表 print(type(res)) print(len(res)) all()的结果就是列表,列表里面是对象 2 只查询某几个字段 # select name as xx,email from user; res…...

13-数据结构-串以及KMP算法,next数组

串 目录 串 一、串: 二、串的存储结构: 三、模式匹配 1.简单模式匹配(BF算法) 2.KMP算法 2.1-next(j)数组手工求解 2.2-nextval(j)数组手工求解 一、串: 内容受…...

Stable Diffusion - 俯视 (from below) 拍摄的人物图像 LoRA 与配置

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/132192139 图像来自 哥特风格 LoRA 俯视 LoRA&#xff0c;提升视觉冲击力&#xff0c;核心配置 <lora:view_from_below:0.6>,(from below,…...

Redis——String类型详解

概述 Redis中的字符串直接按照二进制的数据存储&#xff0c;不会有任何的编码转换&#xff0c;因此存放什么样&#xff0c;取出来的时候就什么样。而MySQL默认的字符集是拉丁文&#xff0c;如果插入中文就会失败 Redis中的字符串类型不仅可以存放文本数据&#xff0c;还可以存…...

Android:换肤框架Android-Skin-Support

gihub地址&#xff1a;https://github.com/ximsfei/Android-skin-support 样例&#xff1a; 默认&#xff1a; 更换后&#xff1a; 一、引入依赖&#xff1a; // -- 换肤依赖implementation skin.support:skin-support:4.0.5// skin-supportimplementation skin.support:ski…...

软件测试面试心得:四种公司、四种问题…

以下是我个人总结的一些经验&#xff1a; 传统开发模式&#xff1a;&#xff36;模式&#xff0c;瀑布模式。传统开发模式往往循规蹈矩&#xff0c;从需求&#xff0c;概要设计&#xff0c;详细设计&#xff0c;开发&#xff0c;单元测试&#xff0c;集成测试&#xff0c;系统测…...

【探索SpringCloud】服务发现-Nacos使用

前言 在聊服务注册中心时&#xff0c;便提到了Nacos。这次便来认识一下。当然&#xff0c;这自然没有官方介绍那般详尽&#xff0c;权当是学习了解Nacos原理的一个过程吧。 Nacos简介 Nacos&#xff0c;全名&#xff1a;dynamic Naming And Configuration Service. 而这个名…...

soap通信2

首先&#xff0c;定义一个XSD&#xff08;XML Schema Definition&#xff09;来描述你的数据结构。在你的Maven项目的src/main/resources目录下&#xff0c;创建一个名为schemas的文件夹&#xff0c;并在其中创建一个名为scriptService.xsd的文件&#xff0c;内容如下&#xff…...

【MySQL】MySQL不走索引的情况分析

未建立索引 当数据表没有设计相关索引时&#xff0c;查询会扫描全表。 create table test_temp (test_id int auto_incrementprimary key,field_1 varchar(20) null,field_2 varchar(20) null,field_3 bigint null,create_date date null );expl…...

JVM垃圾回收篇-垃圾回收算法

JVM垃圾回收篇-垃圾回收算法 标记清除&#xff08;Mark Sweep&#xff09; 概念 collector指的就是垃圾收集器。 mutator是指除了垃圾收集器之外的部分&#xff0c;比如说我们的应用程序本身。 mutator的职责一般是NEW(分配内存)、READ(从内存中读取内容)、WRITE(将内容写入内…...

android APP内存优化

Android为每个应用分配多少内存 Android出厂后&#xff0c;java虚拟机对单个应用的最大内存分配就确定下来了&#xff0c;超出这个值就会OOM。这个属性值是定义在/system/build.prop文件中. 例如&#xff0c;如下参数 dalvik.vm.heapstartsize8m #起始分配内存 dalvik.vm.…...

mysql_docker主从复制_实战_binlog混合模式_天座著

步骤1&#xff1a;拉取镜像 docker pull mariadb:latest 步骤2.1&#xff1a;创建两个文件夹用于放置挂载mysql的my.cnf /tianzuomysqlconf/master /tianzuomysqlconf/slave mkdir /tianzuomysqlconf cd /tianzuomysqlconf mkdir master mkdir slave 步骤2.2&#xff1a;创…...

鸿蒙开发学习笔记1——真机运行hello world

问题背景 学习任何语言和框架的第一步&#xff0c;永远都是跑通熟悉的“hello world”&#xff0c;本文将介绍鸿蒙开发如何跑通“hello world”。 问题分析 一、构建第一个ArkTS应用&#xff08;fa模型&#xff09; 说明&#xff1a;请使用DevEco Studio V3.0.0.601 Beta1及…...

Java数组,简简单单信手沾来~

——数组&#xff0c;一组相同数据类型的数据 一.一维数组 1.数组的基本概念 1&#xff09;数组用于存储多个同一数据类型的数据 2&#xff09;数组是数据类型【引用类型】 3&#xff09;数组的形式&#xff1a;数据类型 [] 4&#xff09;数组的下标从0开始 5&#xff09;数…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...