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

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

前端工具库lodash与lodash-es区别详解

lodash 和 lodash-es 是同一工具库的两个不同版本&#xff0c;核心功能完全一致&#xff0c;主要区别在于模块化格式和优化方式&#xff0c;适合不同的开发环境。以下是详细对比&#xff1a; 1. 模块化格式 lodash 使用 CommonJS 模块格式&#xff08;require/module.exports&a…...

C# WPF 左右布局实现学习笔记(1)

开发流程视频&#xff1a; https://www.youtube.com/watch?vCkHyDYeImjY&ab_channelC%23DesignPro Git源码&#xff1a; GitHub - CSharpDesignPro/Page-Navigation-using-MVVM: WPF - Page Navigation using MVVM 1. 新建工程 新建WPF应用&#xff08;.NET Framework) 2.…...