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

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

椭圆曲线密码学(ECC)

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

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...

P10909 [蓝桥杯 2024 国 B] 立定跳远

# P10909 [蓝桥杯 2024 国 B] 立定跳远 ## 题目描述 在运动会上&#xff0c;小明从数轴的原点开始向正方向立定跳远。项目设置了 $n$ 个检查点 $a_1, a_2, \cdots , a_n$ 且 $a_i \ge a_{i−1} > 0$。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时&#xff0…...