2024王道408数据结构P144 T17

2024王道408数据结构P144 T17

思考过程

  1. 先看题目,让我们判断两棵二叉树是否相似,相似指的是以下三个方面:
    • T1和T2都是空的二叉树或T1和T2都只有一个结点
    • T1的左子树和T2的左子树是相似的,且T1的右子树和T2的右子树是相似的。

题目的意思我们可以简化为两个大类,要么为空要么为非空。请添加图片描述
2. 我们只要判断当前结点是两个都为空还是一个为空另一个不为空就行了,因为如果一个为空另一个不为空则说明这两棵树必不可能相似。如果两个结点都空的话我们函数结果return 1,把一个结点为空另一个结点不空的话函数返回return 0。

代码过程

  1. 正如我们上面所说的,我们需要判断三种情况
    • 如果两个结点都为空的话if(T1 == NULL && T2 == NULL)说明这两棵树必是相似的,我们直接return 1;就好了。
    • 如果两个结点中有一个结点为空if (T1 == NULL || T2 == NULL),另一个结点不为空的话说明这两棵树必不可能相似,我们返回0return 0;
    • 第三种情况就是两个结点都不为空,也就是我们需要用递归来判断剩下的结点是否相似,我们创建两个变量left和right,left用来表示两个结点的左子树是否相似,如果相似的话给我们返回1,不相似则返回0;right也一样,用来表示两个结点的右子树是否相似。假设我们给函数取名叫similarleft = similar(T1->lchild, T2->lchild); right = similar(T1->rchild, T2->rchild);最后返回的时候我们返回return (left && right);用逻辑与&&,左右两边都为1结果才是1,有0则0。

到这里这题就做完了。

完整代码

//
// Created by 黎圣  on 2023/8/26.
//
/** 试设计判断两颗二叉树是否相似的算法。所谓二叉树T1和T2相似,指的是* T1和T2都是空的二叉树* 或都只有一个根结点* 或T1的左子树和T2的左子树是相似的,且T1的右子树和T2的右子树是相似的。*/
#include "iostream"
using namespace std;
typedef struct TreeNode
{char data;struct TreeNode *lchild, *rchild;
}*tree;
void CreateTree(tree &t)
{char ch;cin >> ch;if (ch == '#')t = NULL;else{t = (struct TreeNode *)malloc(sizeof(struct TreeNode));t->data = ch;t->lchild = NULL;t->rchild = NULL;CreateTree(t->lchild);CreateTree(t->rchild);}
}
//递归比较左右子树 空+空 = 1 空+非空 = 0
int similar(tree T1, tree T2)
{int left, right;if (T1 == NULL && T2 == NULL)return 1;else if (T1 == NULL || T2 == NULL)return 0;else{left = similar(T1->lchild, T2->lchild);right = similar(T1->lchild, T2->rchild);return (left && right);}
}
int main()
{tree t1, t2;CreateTree(t1);CreateTree(t2);printf("%d", similar(t1, t2));return 0;
}

最后感谢b站up主@吸血小金鱼,找工作真难呜呜呜呜呜呜

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大数据项目实战(Hadoop集群搭建)

一,搭建大数据集群环境 1.2 Hadoop集群搭建 1.2.1 jdk安装 1.下载jdk (1)在根目录下创建三个子目录以备后用。具体如下: mkdir -p /export/data mkdir -p /export/software mkdir -p /export/servers (2)下载路径: 1、官网下载地址http…

APP UI自动化测试思路总结

首先想要说明一下,APP自动化测试可能很多公司不用,但也是大部分自动化测试工程师、高级测试工程师岗位招聘信息上要求的,所以为了更好的待遇,我们还是需要花时间去掌握的,毕竟谁也不会跟钱过不去。接下来,一…

聊聊工科必备软件MATLAB

1.MATLAB的由来 MATLAB(Matrix Laboratory)最初是由美国的MathWorks公司于1980年代初开发的一种数值计算和科学数据可视化的编程环境。 MATLAB的起源可以追溯到20世纪70年代,在斯坦福大学,科学家Cleve Moler在长期从事数值计算的研…

Java流式编程详细介绍

文章目录 1. 流式编程介绍2. 过滤2.1 filter2.2 distinct2.3 limit2.4 sorted2.5 skip 3. 映射3.1 map3.2 flatmap 4 查找4.1 allMatch4.2 anyMatch4.3 noneMatch4.4 findFirst4.5 findAny 5. 归约6. 收集6.1 counting6.2 maxBy,minBy6.3 summingInt、summingLong、summingDoub…

1+X智慧安防系统实施与运维技能等级证产教融合基地建设方案

一、系统概述 1X智慧安防系统实施与运维技能等级证产教融合体系统融合了产业需求、教育培训和技能认证,通过课程培训、实训基地和实习实训等方式培养学员的技能水平,并通过技能认证来评估其能力,以满足智慧安防行业对人才的需求,并…

iMX6ULL 库移植 | Libgpiod 库的交叉编译及使用指南(linux)

GPIO口的操作,是很常见的功能。传统的GPIO sysfs接口已被弃用。自Linux 4.8起,内核提供了全新的操作gpio的方式libgpiod(C library and tools for interacting with the linux GPIO character device),当然也更高效&am…

Nuxt 菜鸟入门学习笔记三:视图

文章目录 入口文件组件 Components页面 Pages布局 Layouts Nuxt 官网地址: https://nuxt.com/ Nuxt 提供多个组件层来实现应用程序的用户界面。 入口文件 App.vue组件 Components页面 Pages布局 Layouts 下面逐一进行介绍。 入口文件 默认情况下,Nu…

vue3使用Elementplus 动态显示菜单icon不生效

1.问题描述 菜单icon由后端提供&#xff0c;直接用的字符串返回&#xff0c;前端使用遍历显示&#xff0c;发现icon不会显示 {id: 8, path:/userManagement, authName: "用户管理", icon: User, rights:[view]}, <el-menu-item :index"menu.path" v-f…

常用数据库备份方法,sql数据库备份方法

在信息时代&#xff0c;数据成为了公司的主要资产。然而&#xff0c;数据的安全性和完整性也成为企业管理的重要组成部分。因此&#xff0c;数据库备份至关重要。本文将详细介绍几种常见的数据库备份方法。 全备份 全备份是指数据库中所有数据的备份&#xff0c;包括数据文件、…

五、多表查询-4.6练习

一、准备数据 【效果展示】 emp1表&#xff08;员工表&#xff09;&#xff1a; dept1表&#xff08;部门表&#xff09;&#xff1a; salgrade表&#xff08;薪资等级表&#xff09;&#xff1a; 二、案例 1、查询员工的姓名、年龄、职位、部门信息&#xff08;隐式内连接&am…

SpringBoot + layui 框架实现一周免登陆功能

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…

MySQL的日志undolog、binlog、redolog

1. 日志层次 binlog是Server层&#xff0c;undolog和redolog是innodb引擎层特有的。 2. 记录了什么 & 作用 binlog 记录了所有数据库结构变更和表数据修改的SQL日志。 主要用于数据备份和主从复制&#xff0c;比如误删数据了可以用binlog找回。 undolog 如下图&#…

Verilog 实现状态机自动售卖机

Verilog 实现状态机自动售卖机 教学视频&#xff1a;https://www.bilibili.com/video/BV1Ve411x75W?p33&spm_id_frompageDriver&vd_source19ae31dff4056e52d2729a4ca212602b 功能需求 使用1元、2元、5元面值的纸币进行支付&#xff0c;获取6元的物品&#xff0c;不设…

在el-tree懒加载中进行局部刷新

在进行懒加载的树组件中&#xff0c;操作子节点新增、修改以及删除操作时&#xff0c;需要对树组件进行局部刷新&#xff1a; /* 懒加载 */ async loadNode(node, resolve) {if (node.level 0) {// 异步加载根节点数据const data await fn({ parentId: });resolve(data);thi…

linux中学习控制进程的要点

1. 进程创建 1.1 fork函数 #include <unistd.h> pid_t fork(void); 返回值&#xff1a;自进程中返回0&#xff0c;父进程返回子进程id&#xff0c;出错返回-1 进程调用fork&#xff0c;当控制转移到内核中的fork代码后&#xff0c;内核会做以下操作 分配新的内存块和…

19.CSS雨云动画特效

效果 源码 <!DOCTYPE html> <html lang="en"> <head><meta charset="UTF-8"><title>Cloud & Rain Animation</title><link rel="stylesheet" href="style.css"> </head> <bo…

专题:平面、空间直线参数方程下的切线斜率问题

本文研究平面、空间直线在参数方程形式下&#xff0c;切线斜率&#xff08;即导数&#xff09;如何表示的问题。 如上图所示。 设 y f ( x ) &#xff0c; x φ ( t ) &#xff0c; y ψ ( t ) 当 t t 0 时&#xff0c; x x 0 &#xff0c; y y 0 &#xff0c;即点 A 坐…

最简单vue获取当前地区天气--高德开放平台实现

目录 前言 一、注册成为高德平台开发者 二、注册天气key 1.点击首页右上角打开控制台 2.创建新应用 三、vue项目使用 1.打开vue项目找到public下的index.html&#xff0c;如果是vue3的话直接在主目录打开index.html文件就行&#xff0c;主要就是打开出口文件 ​编辑 2.根据高德…

元矿山下的音视频应用

// 近年来&#xff0c;矿业的技术和管理模式随着元宇宙的火爆和自动驾驶技术的发展逐渐变化、升级&#xff0c;进而衍生出元矿山的概念&#xff0c;音视频技术也在其中成为了关键一环。LiveVideoStackCon 2023 上海站邀请了来自希迪智驾的任思亮&#xff0c;为大家分享希迪智…

无限计算力:探索云计算的无限可能性

这里写目录标题 前言云计算介绍服务模型&#xff1a; 应用领域&#xff1a;云计算主要体现在生活中的地方云计算未来发展的方向 前言 云计算是一种基于互联网的计算模型&#xff0c;通过它可以实现资源的共享、存储、管理和处理。它已经成为许多个人、企业和组织的重要技术基础…