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

算法练习第16天|101. 对称二叉树

 101. 对称二叉树

力扣链接icon-default.png?t=N7T8https://leetcode.cn/problems/symmetric-tree/description/

题目描述:

给你一个二叉树的根节点 root , 检查它是否轴对称。

示例 1:

输入:root = [1,2,2,3,4,4,3]
输出:true

示例 2:

输入:root = [1,2,2,null,3,null,3]
输出:false

思路分析:

对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,而不是比较左右子节点。所以在递归遍历的过程中,要同时遍历两棵子树。要比较子树的外侧与内侧。

递归实现 

如果使用递归函数,则递归函数的参数应该是左右子树的根节点指针。同时,判断是否对称需要有bool类型的结果,所以,递归函数的返回值类型可以用bool。其形式如下:

bool compare(TreeNode * left, TreeNode * right){}

如此就完成了递归三部曲中的第一步:确定递归函数的参数和返回值 

因为要遍历两棵树而且要比较内侧和外侧节点,所以准确的来说是一个左子树的遍历顺序是左右中,一个右子树的遍历顺序是右左中。 

递归第二步:确认终止条件

首先需要对传入的两个子树根节点进行分析,一共有一下五种情况:

1.左子树空、右子树非空

2.左子树非空、右子树空

3.左子树空、右子树空

4.左子树非空、右子树非空,对应元素不相等

5.左子树非空、右子树非空,对应元素相等,需要继续判断

//存在右子树,不存在左子树  ---》不对称
if(left == nullptr && right != nullptr) return false;
//存在左子树,不存在右子树  ---》不对称
else if(left != nullptr && right == nullptr) return false;
//左右子树均不存在  ---》对称
else if(left == nullptr && right == nullptr) return true;
//左右子树均存在,但是对应子树根节点元素不相等   --》不对称
else if(left->val != right->val)  return false;

上述代码是前四种情况,属于递归终止条件。

第五种情况就是需要继续遍历判断的,所以它属于递归第三步:确认单层递归逻辑

 递归第三步:确认单层递归逻辑

继续遍历比较时,应该将左子树的左子树同右子树的右子树进行比较,因为这些都属于外侧。同时,还要将左子树的右同右子树的左进行比较,这些属于内侧。所以单层递归的逻辑如下:

//以上情况都不满足,则只剩下左右子树均存在,且子树根节点元素相等的情况。那么需要继续比较
bool outside = compare(left->left, right->right);  //比较外侧,左子树的左与右子树的右比较
bool inside = compare(left->right, right->left);   //比较内侧,左子树的右与右子树的左比较
if(outside && inside)  //外侧内侧都相等return true;
else   //否则return false;

递归整体代码如下:

/*** 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:bool compare(TreeNode * left, TreeNode * right){//存在右子树,不存在左子树  ---》不对称if(left == nullptr && right != nullptr) return false;//存在左子树,不存在右子树  ---》不对称else if(left != nullptr && right == nullptr) return false;//左右子树均不存在  ---》对称else if(left == nullptr && right == nullptr) return true;//左右子树均存在,但是对应子树根节点元素不相等   --》不对称else if(left->val != right->val)  return false;//以上情况都不满足,则只剩下左右子树均存在,且子树根节点元素相等的情况。那么需要继续比较bool outside = compare(left->left, right->right);  //比较外侧,左子树的左与右子树的右比较bool inside = compare(left->right, right->left);   //比较内侧,左子树的右与右子树的左比较if(outside && inside)  //外侧内侧都相等return true;else   //否则return false;}bool isSymmetric(TreeNode* root) {if(root==nullptr) return true;return compare(root->left, root->right);}
};

使用队列实现:

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == NULL) return true;queue<TreeNode*> que;que.push(root->left);   // 将左子树头结点加入队列que.push(root->right);  // 将右子树头结点加入队列while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转TreeNode* leftNode = que.front(); que.pop();TreeNode* rightNode = que.front(); que.pop();if (!leftNode && !rightNode) {  // 左节点为空、右节点为空,此时说明是对称的continue;}// 左右一个节点不为空,或者都不为空但数值不相同,返回falseif ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {return false;}que.push(leftNode->left);   // 加入左节点左孩子que.push(rightNode->right); // 加入右节点右孩子que.push(leftNode->right);  // 加入左节点右孩子que.push(rightNode->left);  // 加入右节点左孩子}return true;}
};

使用栈实现:

class Solution {
public:bool isSymmetric(TreeNode* root) {if (root == NULL) return true;stack<TreeNode*> st; // 这里改成了栈st.push(root->left);st.push(root->right);while (!st.empty()) {TreeNode* leftNode = st.top(); st.pop();TreeNode* rightNode = st.top(); st.pop();if (!leftNode && !rightNode) {continue;}if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {return false;}st.push(leftNode->left);st.push(rightNode->right);st.push(leftNode->right);st.push(rightNode->left);}return true;}
};

相关文章:

算法练习第16天|101. 对称二叉树

101. 对称二叉树 力扣链接https://leetcode.cn/problems/symmetric-tree/description/ 题目描述&#xff1a; 给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true示例 2&#x…...

YOLOV8实战教程——最新安装(截至24.4)

前言&#xff1a;YOLOV8更新比较快&#xff0c;最近用的时候发现有些地方已经跟之前不一样&#xff0c;甚至安装都会出现差异&#xff0c;所以做一个最新版的 yolov8 安装教程 一、Github 或者 GitCode 搜索 ultralytics 下载源码包&#xff0c;下载后解压到你需要安装的位置…...

redis zremove删除不掉【bug】

redis zremove删除不掉【bug】 前言版权redis zremove删除不掉错误产生相关资源EldDataEchartsTestDataService 解决 最后 前言 2024-4-12 20:35:21 以下内容源自《【bug】》 仅供学习交流使用 版权 禁止其他平台发布时删除以下此话 本文首次发布于CSDN平台 作者是CSDN日星…...

对象的本地保存

对象的本地保存 对象的创建和保存 对象的特点&#xff1a; 对象“生活”在内存空间中&#xff0c;因此&#xff0c;程序一旦关闭&#xff0c;这些对象也都会被CLR的垃圾回收机制销毁。程序第二次运行时&#xff0c;对象会以“全新”的状态出现,无法保留上次对象的运行状态。…...

PostgreSQL入门到实战-第二十一弹

PostgreSQL入门到实战 PostgreSQL中表连接操作(五)官网地址PostgreSQL概述PostgreSQL中RIGHT JOIN命令理论PostgreSQL中RIGHT JOIN命令实战更新计划 PostgreSQL中表连接操作(五) 使用PostgreSQL RIGHT JOIN连接两个表&#xff0c;并从右表返回行 官网地址 声明: 由于操作系统…...

李彦宏放话:百度AI大模型绝不抢开发者饭碗

关注卢松松&#xff0c;会经常给你分享一些我的经验和观点。 昨晚&#xff0c;李彦宏内部讲话称&#xff1a;AI大模型开源意义不大&#xff0c;百度绝不抢开发者饭碗。 但你一定要说话算话哦&#xff0c;可千万别说&#xff1a;“我永远不做手机&#xff0c;谁再敢提做手机就给…...

es 倒排索引

es 倒排索引TRee 倒排索引树&#xff08;TRee&#xff09;通常指的是Elasticsearch中用于支持高速搜索的一种数据结构。它是一种树状结构&#xff0c;可以通过特定的词项&#xff08;terms&#xff09;来快速定位包含这些词项的文档。 在Elasticsearch中&#xff0c;倒排索引…...

阿里云服务器公网带宽费用全解析(不同计费模式)

阿里云服务器公网带宽怎么收费&#xff1f;北京地域服务器按固定带宽计费一个月23元/M&#xff0c;按使用流量计费0.8元/GB&#xff0c;云服务器地域不同实际带宽价格也不同&#xff0c;阿里云服务器网aliyunfuwuqi.com分享不同带宽计费模式下带宽收费价格表&#xff1a; 公网…...

python-pytorch实现lstm模型预测文本输出0.1.00

python-pytorch实现lstm模型预测文本输出0.1.00 数据参考效果分词到数组准备数数据查看频次获取vacab生成输入数据训练测试连续预测有问题还需要完善 数据 一篇新闻:https://news.sina.com.cn/c/2024-04-12/doc-inarqiev0222543.shtml 参考 https://blog.csdn.net/qq_1953…...

77、WAF攻防——权限控制代码免杀异或运算变量覆盖混淆加密传参

文章目录 WAF规则webshell免杀变异 WAF规则 函数匹配 工具指纹 webshell免杀变异 php 传参带入 eval可以用assert来替换,assert也可以将字符串当作php代码执行漏洞 php 变量覆盖 php 加密 使用加密算法对php后门进行加密 php 异或运算 简化:无字符webshellP 无数字字母rc…...

A12 STM32_HAL库函数 之 HAL-ETH通用驱动 -- A -- 所有函数的介绍及使用

A12 STM32_HAL库函数 之 HAL-ETH通用驱动 -- A -- 所有函数的介绍及使用 1 通用定时器&#xff08;TIM&#xff09;预览1.1 HAL_ETH_Init1.2 HAL_ETH_DeInit1.3 HAL_ETH_DMATxDescListInit1.4 HAL_ETH_DMARxDescListInit1.5 HAL_ETH_MspInit1.6 HAL_ETH_MspDeInit1.7 HAL_ETH_T…...

Linux从入门到精通 --- 1.初始Linux

文章目录 第一章&#xff1a;1.1 Linux的诞生1.2 Linux系统内核1.3 Linux系统发行版 第一章&#xff1a; 1.1 Linux的诞生 1991年由林纳斯 托瓦兹创立并发展至今称为服务器操作系统领域的核心系统。 1.2 Linux系统内核 Linux内核提供了系统的主要功能&#xff0c;甚至是开源…...

linux使用docker实现redis主从复制和哨兵模式

目录 1. 拉取redis镜像 2.使用可视化redis工具 3. 设置从redis 4.设置哨兵模式 5. 使用docker-compose快速创建 1. 拉取redis镜像 docker pull redis 默认拉取最新的镜像。 然后pull结束后使用docker images检查镜像&#xff1a; 然后docker run创建container容器 首先…...

新版chrome 解决在http协议下无法调用摄像头和麦克风的问题(不安全)

解决办法&#xff1a;亲测可行 chrome浏览器地址栏中输入chrome://flags/#unsafely-treat-insecure-origin-as-secure&#xff0c;回车&#xff0c;如下图&#xff0c;将该选项置为Enabled&#xff0c; edge浏览器打开&#xff1a;edge://flags/#unsafely-treat-insecure-orig…...

机器学习入门项目二(逻辑回归)

如果输入数据长度为2&#xff0c;上一章的方程就无法满足需求了&#xff0c;需要修改方程&#xff1a; z w 1 x w 2 y b zw_1xw_2yb zw1​xw2​yb 数据产生器&#xff1a; import matplotlib.pyplot as plt import numpy as npclass DataGenerator2Input:"""…...

C++类引用的好处

简化代码&#xff1a;引用可以简化代码&#xff0c;使其更加易读和易懂。通过使用引用&#xff0c;可以避免在函数参数中复制大型对象&#xff0c;从而提高代码的效率和性能。 传递大型对象的效率高&#xff1a;使用引用作为函数参数传递大型对象时&#xff0c;不需要进行对象…...

从零自制docker-9-【管道实现run进程和init进程传参】

文章目录 命令行中输入参数长度过长匿名管道从父进程到子进程传参[]*os.File{}os.NewFile和io.ReadAllexe.LookPathsyscall.Execstrings.Split(msgStr, " ")/bin/ls: cannot access : No such file or directory代码 命令行中输入参数长度过长 用户输入参数过长或包…...

全量知识系统 程序详细设计 之 三种“活物” 之1(QA百度搜索 )

Q1. 今天聊聊 全知系统中 三种“活物”。先从他们的一个简单描述开始&#xff1a; 自主&#xff1a;计算机“集群”的“沉”与“浮”&#xff1b; 自然&#xff1a;AI “众生”的“世”和“界” &#xff1b;自由&#xff1a;人类 “公民”的“宇”或“宙”。 全知系统中的三…...

QT 线程之movetothread

上文列举了qt中线程的几种方法&#xff0c;其中2种方法最为常见。 这两种方法都少不了QThread类&#xff0c;前者继承于QThread类&#xff0c;后者复合QThread类。 本文以实例的方式描述了movetothread&#xff08;&#xff09;这种线程的方法&#xff0c;将QObject的子类移动…...

如何处理ubuntu22.04LTS安装过程中出现“Daemons using outdated libraries”提示

Ubuntu 22.04 LTS 中使用命令行升级软件或安装任何新软件时&#xff0c;您可能收到“Daemons using outdated libraries”&#xff0c;“Which services should be restarted?”的提示&#xff0c;提示下面列出备选的重启服务&#xff0c;如下。 使用以下命令&#xff0c;能够…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...