leetcode101. 对称二叉树,递归法+迭代法详解附代码

leetcode101. 对称二叉树

给你一个二叉树的根节点 root , 检查它是否轴对称。
示例 1:
在这里插入图片描述
输入:root = [1,2,2,3,4,4,3]
输出:true

示例 2:在这里插入图片描述
输入:root = [1,2,2,null,3,null,3]
输出:false

递归法

1.定义辅助函数 check:这个函数接收两个参数,分别是指向二叉树节点的指针 p 和 q。它的作用是递归地检查从 p 和 q 出发的子树是否镜像对称。

2.处理空节点情况:在 check 函数中,首先检查 p 和 q 是否都为空。如果都为空,则说明这两个子树是对称的,返回 true。如果其中一个为空而另一个不为空,则说明这两个子树不对称,返回 false。

3.比较节点值:如果 p 和 q 都不为空,接下来比较它们的值。如果值不相等,则说明这两个子树不对称,返回 false。

4.递归检查子树:如果 p 和 q 的值相等,算法会继续递归地检查 p 的左子树和 q 的右子树是否对称,以及 p 的右子树和 q 的左子树是否对称。这一步骤是关键,因为它确保了对称性的检查是全面的。只有当这两个递归调用都返回 true 时,check 函数才会返回 true。

5.实现主函数 isSymmetric:这个函数是对外的接口,它接收一个参数 root,即二叉树的根节点。isSymmetric 函数通过调用 check 函数并传入 root 和 root 作为参数来实现对整个二叉树的对称性检查。这意味着算法会从根节点出发,检查其左右子树是否镜像对称。

递归法具体代码如下:

class Solution {
public:bool check(TreeNode *p, TreeNode *q) {if (!p && !q) return true;if (!p || !q) return false;return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);}bool isSymmetric(TreeNode* root) {return check(root, root);}
};

迭代法

递归代码变成迭代,往往需要辅助队列或者辅助栈,我们这里使用辅助队列。

初始节点入队列:首先把root节点两次入辅助队列。

层序遍历:使用一个 while 循环进行层序遍历,直到队列为空。在每次循环中,从队列中取出两个节点 u 和 v。

处理空节点:如果 u 和 v 都为空,说明当前层的两个节点是对称的,继续处理下一层。如果其中一个为空而另一个不为空,或者它们的值不相等,说明这两个子树不对称,函数返回 false。

对称性检查:如果 u 和 v 的值相等,算法会将 u 的左子节点和 v 的右子节点,以及 u 的右子节点和 v 的左子节点入队。这样,下一次循环时,它们会被取出并进行比较,确保左子节点与右子节点的值相等,从而保证对称性。

迭代法完整代码如下:

class Solution {
public:bool check(TreeNode *u, TreeNode *v) {queue <TreeNode*> q;q.push(u); q.push(v);while (!q.empty()) {u = q.front(); q.pop();v = q.front(); q.pop();if (!u && !v) continue;if ((!u || !v) || (u->val != v->val)) return false;q.push(u->left); q.push(v->right);q.push(u->right); q.push(v->left);}return true;}bool isSymmetric(TreeNode* root) {return check(root, root);}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3249494.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Python算法实现之排序算法的Python实现详解

概要 排序算法是计算机科学中最基础和最重要的算法之一。它们在数据处理中起着关键作用,广泛应用于搜索、数据分析和优化等领域。本文将详细介绍几种常见的排序算法及其Python实现,包括冒泡排序、选择排序、插入排序、归并排序和快速排序,并通过具体示例代码展示它们的工作…

qml 实现一个listview

主要通过qml实现listvie功能&#xff0c;主要包括右键菜单&#xff0c;滚动条&#xff0c;拖动改变内容等&#xff0c;c 与 qml之间的变量和函数的调用。 main.cpp #include <QQuickItem> #include <QQmlContext> #include "testlistmodel.h" int main…

19-2 LLM之野望 2 - LLM给到Quora面临的困境

Quora 有一个简单的前提&#xff1a;它是一个分享知识和专业知识的地方&#xff0c;好奇的人可以就任何可以想象到的话题提出问题&#xff0c;并从平台博学的社区获得深思熟虑的、见识广博的答案。 想想雅虎答案 (Yahoo Answers)&#xff0c;它适用于技术员工和格拉德威尔式的…

C#语法基础详解(万字总结)

文章目录 **参考书籍&#xff1a;C#7.0 核心技术指南**类型类字段解构器对象初始化器属性表达式属性(只读属性才可以)自动属性属性初始化器 索引器静态构造器nameof运算符 继承类型转换和引用转换as运算符is运算符is与模式变量 虚函数成员抽象类和抽象成员new和重写base关键字构…

1. 个人谈心 ——【如何学习编程及合理安排休息时间】

&#x1f4d6; 声明 ! ! ! 此文章仅仅属于个人思想&#xff0c;如有不满或者意见不相同&#xff0c;可以在评论区讨论留言&#xff0c;非常感谢支持&#xff01;&#xff01;&#xff01; &#x1f495;个人主页&#xff1a;三亿老奶奶心中的梦 &#x1f4d8;收录专栏&#xff…

【贪心算法】力扣1481.不同整数的最少数目

给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素&#xff0c;请找出移除后数组中不同整数的最少数目。 示例 1&#xff1a; 输入&#xff1a;arr [5,5,4], k 1 输出&#xff1a;1 解释&#xff1a;移除 1 个 4 &#xff0c;数组中只剩下 5 一种整数。…

docker默认存储地址 var/lib/docker 满了,换个存储地址操作流程

1. 查看docker 存储地址 docker info如下 var/lib/docker2、查看内存大小 按需执行 df -h 找超过100M的大文件 find / -type f -size 100M -exec ls -lh {} \; df -Th /var/lib/docker 查找这个文件的容量 df -h 查找所有挂载点 du -hs /home/syy_temp/*1、df -h 2、sud…

IDEA关联数据库

《IDEA破解、配置、使用技巧与实战教程》系列文章目录 第一章 IDEA破解与HelloWorld的实战编写 第二章 IDEA的详细设置 第三章 IDEA的工程与模块管理 第四章 IDEA的常见代码模板的使用 第五章 IDEA中常用的快捷键 第六章 IDEA的断点调试&#xff08;Debug&#xff09; 第七章 …

移动设备安全革命:应对威胁与解决方案

移动设备已成为我们日常工作和家庭生活中不可或缺的工具&#xff0c;然而&#xff0c;对于它们安全性的关注和投资仍然远远不够。本文深入分析了移动设备安全的发展轨迹、目前面临的威胁态势&#xff0c;以及业界对于这些安全漏洞响应迟缓的深层原因。文中还探讨了人们在心理层…

自动驾驶系列—智能巡航辅助功能中的横向避让功能介绍

文章目录 1. 背景介绍2. 功能定义3. 功能原理4. 传感器架构5. 实际应用案例5.1 典型场景1&#xff1a;前方车辆压线5.2 典型场景2&#xff1a;相邻车道有大型车辆5.3 典型场景3&#xff1a;它车近距离cut in 6. 总结与展望 1. 背景介绍 随着汽车技术的发展&#xff0c;智能巡航…

AWS基础知识

VPC (Virtual Private Cloud): 参考&#xff1a;https://docs.aws.amazon.com/vpc/latest/userguide/what-is-amazon-vpc.html With Amazon Virtual Private Cloud (Amazon VPC), you can launch AWS resources in a logically isolated virtual network that you’ve defined…

fastJSON 解决kafka消息斜杠转义问题

Bug: kafka发送消息时的JSON转义异常 问题描述: 问题描述:kafka消息发送出去但是消费者执行相关逻辑的时候报错. 场景:当时实习的时候需要模拟数据做一个实时经纬度传输的接口,使用kafka实时发送消息将数据同步到数据库中 问题分析: fastjson使用不当可能导致转义异常**,kafka…

【iOS】——内存对齐

内存对齐是什么 内存对齐指的是数据在内存中的布局方式&#xff0c;它确保每个数据类型的起始地址能够满足该类型对齐的要求。这是因为现代处理器在访问内存时&#xff0c;如果数据的起始地址能够对齐到一定的边界&#xff0c;那么访问速度会更快。这种对齐通常是基于数据类型…

git使用、git与idea结合、gitee、gitlab

本文章基于黑马程序javase模块中的"git"部分 先言:git在集成idea中,不同版本的idea中页面显示不同,操作时更注重基于选项的文字;git基于命令操作参考文档实现即可,idea工具继承使用重点掌握 1.git概述 git是目前世界上最先进的分布式文件版本控制系统 分布式:将…

Linux-交换空间(Swap)管理

引入概念 在计算机中&#xff0c;硬盘的容量一般比内存大&#xff0c;内存&#xff08;4GB 8GB 16GB 32GB 64GB…&#xff09;&#xff0c;硬盘&#xff08;512GB 1T 2T…&#xff09;。 冯诺依曼的现代计算机结构体系里面的存储器就是内存 内存是一种易失性存储器&#xff0c…

【论文解读】VoxelNeXt: Fully Sparse VoxelNet for 3D Object Detection and Tracking

VoxelNeXt 摘要引言方法Sparse CNN Backbone AdaptationSparse Prediction Head 3D Tracking实验结论 摘要 3D物体检测器通常依赖于手工制作的方法&#xff0c;例如锚点或中心&#xff0c;并将经过充分学习的2D框架转换为3D。因此&#xff0c;稀疏体素特征需要通过密集预测头进…

rabbitmq生产与消费

一、rabbitmq发送消息 一、简单模式 概述 一个生产者一个消费者模型 代码 //没有交换机&#xff0c;两个参数为routingKey和消息内容 rabbitTemplate.convertAndSend("test1_Queue","haha");二、工作队列模式 概述 一个生产者&#xff0c;多个消费者&a…

【Django】网上蛋糕商城后台-类目管理

1.类目管理列表实现 当管理员进入后台管理后&#xff0c;点击类目管理&#xff0c;向服务器发出请求 path(admin/type_list/,viewsAdmin.type_list), # 处理商品分类管理列表请求 def type_list(request):# 读取分页页码try:ym request.GET["ym"]except:ym 1# 查…

html2canvas + jspdf 纯前端HTML导出PDF的实现与问题

前言 这几天接到一个需求&#xff0c;富文本编辑器的内容不仅要展示出来&#xff0c;还要实现展示的内容导出pdf文件。一开始导出pdf的功能是由后端来做的&#xff0c;然后发现对于宽度太大的图片&#xff0c;导出的pdf文件里部分图片内容被遮盖了&#xff0c;但在前端是正常显…

Spring Boot1(概要 入门 Spring Boot 核心配置 YAML JSR303数据校验 )

目录 一、Spring Boot概要 1. SpringBoot优点 2. SpringBoot缺点 二、Spring Boot入门开发 1. 第一个SpringBoot项目 项目创建方式一&#xff1a;使用 IDEA 直接创建项目 项目创建方式二&#xff1a;使用Spring Initializr 的 Web页面创建项目 &#xff08;了解&#…