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

【王道数据结构】【chapter5树与二叉树】【P159t16】

试设计判断两棵二叉树是否相似的算法。所谓二叉树T1和T2相似,指的是T1和T2都是空的二叉树或都只有一个根节点;或者T1的左子树和T2的左子树是相似的,且T1的右子树和T2的右子树是相似的

#include <iostream>
#include <stack>
#include <queue>
typedef struct treenode{char data;struct treenode *left;struct treenode *right;
}treenode,*ptreenode;ptreenode buytreenode(char x)
{ptreenode n=(ptreenode) malloc(sizeof (treenode));n->data=x;n->left= nullptr,n->right= nullptr;return n;
}
ptreenode build_tree1()
{ptreenode root= buytreenode('A');root->left= buytreenode('B');root->right= buytreenode('C');root->left->left= buytreenode('D');root->left->right= buytreenode('E');root->right->left= buytreenode('F');root->right->right= buytreenode('G');root->left->left->left= buytreenode('H');root->left->left->right= buytreenode('I');return root;
}ptreenode build_tree2()
{ptreenode root= buytreenode('A');root->left= buytreenode('B');root->right= buytreenode('C');root->left->left= buytreenode('D');root->left->right= buytreenode('E');root->right->left= buytreenode('F');root->right->right= buytreenode('G');root->left->left->left= buytreenode('H');root->left->left->right= buytreenode('I');root->left->right->left= buytreenode('J');root->left->right->right= buytreenode('K');root->right->left->left= buytreenode('L');root->right->left->right= buytreenode('M');root->right->right->left= buytreenode('N');root->right->right->right= buytreenode('O');return root;
}ptreenode build_tree3()
{ptreenode root= buytreenode('Z');root->left= buytreenode('Y');root->right= buytreenode('W');root->left->left= buytreenode('X');root->left->right= buytreenode('E');root->right->left= buytreenode('F');root->right->right= buytreenode('G');root->left->left->left= buytreenode('H');root->left->left->right= buytreenode('I');root->left->right->left= buytreenode('J');root->left->right->right= buytreenode('K');root->right->left->left= buytreenode('L');root->right->left->right= buytreenode('M');root->right->right->left= buytreenode('N');root->right->right->right= buytreenode('O');return root;
}
void print_tree(ptreenode root) {std::queue<ptreenode> tmp;tmp.push(root);int s = tmp.size();while (!tmp.empty()) {ptreenode t = tmp.front();tmp.pop();s--;printf("%3c", t->data);if (t->left) tmp.push(t->left);if (t->right) tmp.push(t->right);if (s == 0) puts(""), s = tmp.size();}
}bool isSimilar(ptreenode root1,ptreenode root2)
{if(root1== nullptr&&root2== nullptr) return true;if(root1== nullptr||root2== nullptr) return false;return isSimilar(root1->left,root2->left)&& isSimilar(root1->right,root2->right);
}
int main() {ptreenode root1=build_tree1();ptreenode root2=build_tree2();ptreenode root3=build_tree3();printf("tree1:\n");print_tree(root1);printf("tree2:\n");print_tree(root2);printf("tree3:\n");print_tree(root3);if(isSimilar(root1,root2)) printf("tree1 and tree2 are similar");else printf("tree1 and tree2 are different\n");if(isSimilar(root2,root3)) printf("tree2 and tree3 are similar");else printf("tree2 and tree3 are different");return 0;
}

相关文章:

【王道数据结构】【chapter5树与二叉树】【P159t16】

试设计判断两棵二叉树是否相似的算法。所谓二叉树T1和T2相似&#xff0c;指的是T1和T2都是空的二叉树或都只有一个根节点&#xff1b;或者T1的左子树和T2的左子树是相似的&#xff0c;且T1的右子树和T2的右子树是相似的 #include <iostream> #include <stack> #inc…...

代码随想录算法训练营第51天 | 139.单词拆分 多重背包理论基础

单词拆分 这道题最后是判断能否组成&#xff0c;很像回溯法的问题形式&#xff0c;和分割回文串那道题比较类似&#xff0c;所以是可以用回溯法解决的&#xff0c;但是回溯法需要使用记忆化递归来避免超时。 class Solution{ public:bool backtracking(const string s, const …...

weilai8游戏爬虫

#!/usr/bin/python # -*- coding: UTF-8 -*- #!/usr/bin/python # -*- coding: UTF-8 -*- import os,csv import re import random import time import requests from lxml import etreefrom urllib.parse import quote, unquotepage98 sess requests.Session()#创建一个sessi…...

【Java程序设计】【C00261】基于Springboot的休闲娱乐代理售票系统(有论文)

基于Springboot的休闲娱乐代理售票系统&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的休闲娱乐代理售票系统 本系统分为系统功能模块、管理员功能模块以及用户功能模块。 系统功能模块&#xff1a;休闲娱乐代理…...

【Linux】学习-基础IO拓展篇

Linux基础IO拓展篇—详解文件系统 理解文件系统 在Linux基础IO篇中&#xff0c;我们站在用户的视角对文件进行了理解&#xff0c;主要是针对被打开的文件&#xff0c;那么有没有没有被打开的文件呢&#xff1f;当然有&#xff01;今天我们换个视角&#xff0c;来站在系统的角…...

算法详解(力扣141——环形链表系列)

博主ID&#xff1a;代码小豪 文章目录 环形链表环形链表的性质分析快慢指针法指针的追及相遇问题 环形链表&#xff08;2&#xff09; 环形链表 先来看看环形链表的原题&#xff1a; 中间的部分叙述有点繁杂&#xff0c;简单来概括就是&#xff0c;假如有一个节点&#xff0c…...

浅谈路由器交换结构

一、路由器技术概述 路由器&#xff08;Router&#xff09;是连接两个或多个网络的硬件设备&#xff0c;在网络间起网关的作用&#xff0c;是读取每一个数据包中的地址然后决定如何传送的专用智能性的网络设备。它能够理解不同的协议&#xff0c;例如某个局域网使用的以太网协议…...

Linux第51步_移植ST公司的linux内核第3步_添加修改设备树

1、设备树文件的路径 1)、创建linux中的设备树头文件 在“my_linux/linux-5.4.31/arch/arm/boot/dts/”目录中&#xff0c;以“stm32mp15xx-edx.dtsi”为蓝本&#xff0c;复制一份&#xff0c;并命名为 “stm32mp157d-atk.dtsi”&#xff0c;这就是我们开发板的设备树头文件。…...

【PyTorch】PyTorch中张量(Tensor)统计操作

PyTorch深度学习总结 第五章 PyTorch中张量(Tensor)统计操作 文章目录 PyTorch深度学习总结前言一、最值查找二、特殊值查询 前言 上文介绍了PyTorch中张量(Tensor)的计算操作&#xff0c;本文将介绍张量的统计操作。 一、最值查找 函数描述torch.max()找出张量中的最大值to…...

安卓游戏开发框架应用场景以及优劣分析

一、引言 在移动游戏开发领域&#xff0c;选择合适的开发框架是项目成功的关键因素之一。特别是对于安卓平台&#xff0c;由于其开放性和庞大的用户基础&#xff0c;不同的游戏开发框架应运而生&#xff0c;旨在帮助开发者高效地构建游戏应用。以下是一些流行的安卓游戏开发框架…...

单片机学习笔记---LCD1602

LCD1602介绍 LCD1602&#xff08;Liquid Crystal Display&#xff09;液晶显示屏是一种字符型液晶显示模块&#xff0c;可以显示ASCII码的标准字符和其它的一些内置特殊字符&#xff08;比如日文的片假名&#xff09;&#xff0c;还可以有8个自定义字符 显示容量&#xff1a;…...

django中实现适配器模式

在Django中实现适配器模式&#xff08;Adapter Pattern&#xff09;涉及到创建一个适配器类&#xff0c;它允许不兼容的接口之间进行交互。适配器模式通常用于将一个类的接口转换为另一个客户端期望的接口。 一&#xff1a;实现例子 下面是一个简单的例子&#xff0c;演示如何…...

题记(42)--EXCEL排序

目录 一、题目内容 二、输入描述 三、输出描述 四、输入输出示例 五、完整C语言代码 一、题目内容 Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。 对每个测试用例&#xff0c;首先输出1行“Case i:”&#xff0c;其中 i 是测试用例的编号&#…...

【学网攻】 第(28)节 -- OSPF虚链路

系列文章目录 目录 系列文章目录 文章目录 前言 一、什么是OSPF虚链路&#xff1f; 二、实验 1.引入 实验目标 实验背景 技术原理 实验步骤 实验设备 实验拓扑图 实验配置 扩展 实验拓扑图 实验配置 实验验证 文章目录 【学网攻】 第(1)节 -- 认识网络【学网攻…...

百面嵌入式专栏(面试题)驱动开发面试题汇总1.0

沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇我们将介绍驱动开发面试题 。 1、Linux驱动程序的功能是什么? 对设备初始化和释放。进行内核与硬件的数据交互。检测和处理设备出现的错误。2、内核程序中申请内存使用什么函数? 答案:kmalloc()、kzalloc()、vm…...

Starknet 的 JavaScript 库:Starknet.js、get-starknet和starknet-react

文章目录 Starknet 的 JavaScript 库Starknet.jsget-starknetstarknet-reactStarknet 的 JavaScript 库Starknet.js 官方:https://www.starknetjs.com/ Starknet.js 是一个与 Starknet 交互的 JavaScript 库,通常以脚本或去中心化形式进行交互应用程序。 Starknet.js 的灵感…...

debian11 安装 k8s,containerd ,阿里云镜像(已成功)

1. 环境准备 系统要求&#xff1a;至少 2GB RAM&#xff08;建议 4GB 或更多&#xff09;&#xff0c;网络连接。 节点准备&#xff1a;至少 3 台机器&#xff0c;1 台作为 Master 节点&#xff0c;2 台作为 Worker 节点。 安装sudo apt update apt install sudo设置主机名&a…...

Spring Task定时任务

目录 1、介绍 2、cron表达式 2.1、在线生成器 2.2、通配符 3、代码示例 3.1、使用步骤 3.2、 代码开发 3.3、测试 &#x1f343;作者介绍&#xff1a;双非本科大三网络工程专业在读&#xff0c;阿里云专家博主&#xff0c;专注于Java领域学习&#xff0c;擅长web应用开发…...

【设计模式】23中设计模式笔记

设计模式分类 模板方法模式 核心就是设计一个部分抽象类。 这个类具有少量具体的方法&#xff0c;和大量抽象的方法&#xff0c;具体的方法是为外界提供服务的点&#xff0c;具体方法中定义了抽象方法的执行序列 装饰器模式 现在有一个对象A&#xff0c;希望A的a方法被修饰 …...

类加载过程介绍

一、类的生命周期 类被加载到jvm虚拟机内存开始&#xff0c;到卸载出内存为止&#xff0c;他的生命周期可以分为&#xff1a;加载->验证->准备->解析->初始化->使用->卸载。 其中验证、准备、解析统一称为链接阶段 1、加载 将类的字节码载入方法区中&#xf…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...