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

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

(二)原型模式

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

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...