【算法与数据结构】101、LeetCode对称二叉树
文章目录
- 一、题目
- 二、递归法
- 三、迭代法
- 三、完整代码
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目


二、递归法
思路分析:这道题目标就是要对比左右两半的树是否对称,因此对比不是左右节点是否相等,而是根节点的左子树和右子树是否相等。刚开始笔者想到的是做层序遍历,然后判断每层的值是否前后对称,但是由于层序遍历当中空节点是不显示的,因此例二也会判成对称树。为此我们可以把空节点也显示出来,但是这样一来遍历的节点数量要大于等于树本身非空节点的数量,徒增计算量。经过一番思考,还是想用递归法实现。程序当中我们对比两个结点是否相等,一共有四种情况。其实还有一种情况,就是节点1的值等于节点2的值,这部分判断包含在cmpTree函数的递归语句return当中,如果出现第五种情况,最终会以第一种情况的形式返回。
- 1.节点1、节点2为空,对称,返回true;
- 2.节点1为空、节点2不为空, 不对称,返回false;
- 3.节点1不为空、节点2为空, 不对称,返回false;
- 4.节点1不为空、节点2不为空, 但值不相等,不对称,返回false;
程序如下:
class Solution {
public:// 递归法bool cmpTree(TreeNode* node1, TreeNode* node2) {if (node1 == NULL && node2 == NULL) return true; // 二者均为空节点if (node1 == NULL || node2 == NULL || node1->val != node2->val) return false; // 其他三种情况return cmpTree(node1->left, node2->right) && cmpTree(node1->right, node2->left);}bool isSymmetric(TreeNode* root) {if (root == NULL) return true;return cmpTree(root->left, root->right);}
};
三、迭代法
思路分析:迭代法使用了队列,先将根节点的左右节点压入队中,然后判断语句的思路和递归当中一致,最后再将要比较的节点按顺序入队,注意节点1的左节点和节点2的右节点比较,节点1的右节点和节点2的左节点比较。
class Solution2 {
public:// 迭代法bool isSymmetric(TreeNode* root) {if (!root) return true; // 根节点为空,直接返回queue<TreeNode*> que;que.push(root->left);que.push(root->right);while (!que.empty()) {TreeNode* node1 = que.front(); que.pop();TreeNode* node2 = que.front();que.pop();if (!node1 && !node2) continue;if (!node1 || !node2 || node1->val != node2->val) return false;que.push(node1->left);que.push(node2->right);que.push(node1->right);que.push(node2->left);}return true;}
};
三、完整代码
# include <iostream>
# include <vector>
# include <queue>
# include <string>
# include <stack>
using namespace std;// 树节点定义
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 cmpTree(TreeNode* node1, TreeNode* node2) {if (node1 == NULL && node2 == NULL) return true; // 二者均为空节点if (node1 == NULL || node2 == NULL || node1->val != node2->val) return false; // 其他三种情况return cmpTree(node1->left, node2->right) && cmpTree(node1->right, node2->left);}bool isSymmetric(TreeNode* root) {if (root == NULL) return true;return cmpTree(root->left, root->right);}
};class Solution2 {
public:// 迭代法bool isSymmetric(TreeNode* root) {if (!root) return true; // 根节点为空,直接返回queue<TreeNode*> que;que.push(root->left);que.push(root->right);while (!que.empty()) {TreeNode* node1 = que.front(); que.pop();TreeNode* node2 = que.front();que.pop();if (!node1 && !node2) continue;if (!node1 || !node2 || node1->val != node2->val) return false;que.push(node1->left);que.push(node2->right);que.push(node1->right);que.push(node2->left);}return true;}
};void my_print2(vector<vector<int>>& v, string str) {cout << str << endl;for (vector<vector<int>>::iterator vit = v.begin(); vit < v.end(); ++vit) {for (vector<int>::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {cout << *it << ' ';}cout << endl;}
}// 前序遍历递归法创建二叉树,每次迭代将容器首元素弹出(弹出代码还可以再优化)
void Tree_Generator(vector<string>& t, TreeNode*& node) {if (t[0] == "NULL" || !t.size()) return; // 退出条件else {node = new TreeNode(stoi(t[0].c_str())); // 中t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->left); // 左t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->right); // 右}
}vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size(); // size必须固定, que.size()是不断变化的vector<int> vec;for (int i = 0; i < size; ++i) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left); // 空节点不入队if (node->right) que.push(node->right);}result.push_back(vec);}return result;
}int main()
{vector<string> t = { "1", "2", "3", "NULL", "NULL", "4", "NULL", "NULL", "2", "4", "NULL", "NULL", "3", "NULL", "NULL" }; // 前序遍历//vector<string> t = { "1", "2", "NULL", "3", "NULL", "NULL", "2", "NULL", "3", "NULL", "NULL" }; // 前序遍历TreeNode* root = new TreeNode();Tree_Generator(t, root);vector<vector<int>> tree = levelOrder(root);my_print2(tree, "目标树:");Solution2 s1;bool result = s1.isSymmetric(root);if (result) cout << "对称树" << endl;else cout << "非对称树" << endl;system("pause");return 0;
}
end
相关文章:
【算法与数据结构】101、LeetCode对称二叉树
文章目录 一、题目二、递归法三、迭代法三、完整代码 所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、递归法 思路分析:这道题目标就是要对比左右两半的树是否对称,因此对比不是左右节点是否相等&…...
【N32L40X】学习笔记04-gpio中断库
gpio中断 该函数库的目的就是在统一的地方配置,将配置的不同项放置在一个结构体内部使用一个枚举来定义一个的别名 NVIC 寄存器 NVIC 相关的寄存器定义了可以在 core_cm4.h 文件中找到。我们直接通过程序的定义来分 析 NVIC 相关的寄存器,其定义如下…...
Godot 4 着色器 - Shader调试
我之前用OpenCV进行图像相关处理,觉得已经很不错,结合GDI可以实现流畅的动画效果 直到近来用Shader后才发现,着色器更上一层楼,原来这是入了GPU的坑 Shader编程限制很多,各种不支持,看在它性能不错功能炫…...
liunx时间慢几分钟,定时更新系统时间
#!/bin/sh hwclock --hctosys echo "执行成功" 定时5分钟执行一次...
C# 委托详解
一.委托的概念 C#中委托也叫代理,委托提供了后期绑定机制(官方解释),功能类似于C中的函数指针,它存储的就是一系列具有相同签名和返回类型的方法的地址,调用委托的时候,它所包含的所有方法都会被执行。 二.委托的用法…...
chatGPT 学习分享:内含PPT分享下载
InstructGPT论文地址: Training language models to follow instructions with human feedbackchatGPT地址:openAI个人整理的PPT(可编辑),下载地址:chatGPT学习分享PPT...
使用CRM进行数据分析的四大好处
使用CRM数据分析系统够帮助企业更好地了解客户需求和行为习惯,提供个性化的服务,从而提高客户满意度和忠诚度。使用CRM数据分析系统可以为企业带来一些好处,包括提高客户洞察力、加强营销策略、提高运营效率等。 1.提高客户洞察力:…...
Excel“牛人”变现方案参考
有几种方式可以通过Excel技能实现变现: 1. 提供Excel咨询和培训服务:如果你对Excel非常熟悉,你可以提供咨询和培训服务,帮助他人解决Excel使用中的问题或提高他们的Excel技能。 2. 制作和销售Excel模板:你可以根据市…...
vscode和jetbrains IDEA添加免费的gpt代码生成插件
vscode和jetbrains IDEA添加免费的gpt代码生成插件 VSCODE添加代码智能生成插件 一、打开vscode添加扩展 打开vscode,点击扩展,搜索 aws toolkit 二、连接到AWS 如图,选择添加connectiong to aws 选择 Sign up or Sign in …...
【C#】医学实验室云LIS检验信息系统源码 采用B/S架构
基于B/S架构的医学实验室云LIS检验信息系统,整个系统的运行基于WEB层面,只需要在对应的工作台安装一个浏览器软件有外网即可访问,技术架构:Asp.NET CORE 3.1 MVC SQLserver Redis等。 一、系统概况 本系统是将各种生化、免疫、…...
linux:AWS LightSail 设置虚拟内存
参考: https://www.cnblogs.com/fallin/p/13186236.html 总结: #2G的swap文件 sudo dd if/dev/zero of/swapfile bs1M count2048 sudo chmod 600 /swapfile sudo mkswap /swapfile sudo swapon /swapfile sudo echo /swapfile none swap defaults 0 0 &g…...
“华为杯”研究生数学建模竞赛2016年-【华为杯】E题:粮食最低收购价问题研究
目录 摘 要: 第 1 章 前 言 1.1 研究的目的与意义 1.2 文献综述...
idea项目依赖全部找不到
目录 1,出错现象2,解决3,其他尝试 1,出错现象 很久没打开的Java项目,打开之后大部分依赖都找不到,出现了所有的含有import语句的文件都会报错和一些注解报红报错,但pom文件中改依赖是确实被引入…...
自动驾驶数据标注有哪些?
自动驾驶汽车:人工智能(AI)的焦点 人工智能驱动汽车解决方案的市场规模预计到 2025年将增长十倍以上,提升车内体验的商机领域以及 AI 模型的无偏见训练数据的重要性。在本篇中,我们将介绍车外体验的关键组成部分,以及自动驾驶数据…...
ChatGPT:人工智能语言模型的巅峰之作
一、 ChatGPT 的前世今生 ChatGPT 是 GPT(Generative Pre-trained Transformer)系列模型的最新成员,其前身 GPT-3 在推出后引起了广泛关注。OpenAI 团队不断优化和训练,终于推出了 ChatGPT,这一最先进的语言模型&#…...
【unity之IMGUI实践】敌方逻辑封装实现【六】
👨💻个人主页:元宇宙-秩沅 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 秩沅 原创 👨💻 收录于专栏:uni…...
llvm向用户抛出warning、error信息
1、抛出error信息并终止程序 使用DiagnosticInfoUnsupported可以向用户抛出error信息并且终止程序,效果如同report_fatal_error、Error。后端用法如下: void xxxx::reportErrorMsg(const MachineFunction &MF)const {const Function &F MF.ge…...
微服务学习笔记-----Nacos安装教程(Windows和Linux版本)
Nacos安装教程 Nacos安装指南1.Windows安装1.1.下载安装包1.2.解压1.3.端口配置1.4.启动1.5.访问 2.Linux安装2.1.安装JDK2.2.上传安装包2.3.解压2.4.端口配置2.5.启动 3.Nacos的依赖 Nacos安装指南 1.Windows安装 开发阶段采用单机安装即可。 1.1.下载安装包 在Nacos的Git…...
程序员面试系列,docker常见面试题
原文链接 什么是Docker?它的主要作用是什么?Docker和虚拟机之间有什么区别?Docker的主要组件有哪些?Docker镜像和容器的区别是什么?如何构建Docker镜像?请简要描述构建过程。如何创建和启动一个Docker容器…...
Linux centos7.x系统将/home磁盘分配给/
1.解除挂载并删除/home卷 umount /home如果出现以下报错 : 可以使用以下命令查看哪些进程在占用 fuser -mv /home杀死这些进程就行 kill -9 进程号然后再执行umount /home就可以成功了 , 同时执行以下命令把逻辑卷删除了 lvremove /dev/centos/home…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
