python树的同构学习笔记
作者:小白专场 发布时间:2022-10-23 02:06:29
标签:python,树的同构
一、题意理解
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构的”。现给定两棵树,请你判断它们是否是同构的。
输入格式:输入给出2棵二叉树的信息:
先在一行中给出该树的结点树,随后N行
第i行对应编号第i个结点,给出该结点中存储的字母、其左孩子结点的编号、右孩子结点的编号
如果孩子结点为空,则在相应位置给出“-”
如下图所示,有多种表示的方式,我们列出以下两种:
二、求解思路
搜到一篇也是讲这个的,但是那篇并没有完全用到单向链表的方法,所以研究了一下,写了一个是完全用单向链表的方法:
其实应该有更优雅的删除整个单向列表的方法,比如头设为none,可能会改进下?
# python语言实现
L1 = list(map(int, input().split()))
L2 = list(map(int, input().split()))
# 节点
class Node:
def __init__(self, coef, exp):
self.coef = coef
self.exp = exp
self.next = None
# 单链表
class List:
def __init__(self, node=None):
self.__head = node
# 为了访问私有类
def gethead(self):
return self.__head
def travel(self):
cur1 = self.__head
cur2 = self.__head
if cur1.next != None:
cur1 = cur1.next
else:
print(cur2.coef, cur2.exp, end="")
return
while cur1.next != None:
print(cur2.coef, cur2.exp, end=" ")
cur1 = cur1.next
cur2 = cur2.next
print(cur2.coef, cur2.exp, end=" ")
cur2 = cur2.next
print(cur2.coef, cur2.exp, end="")
# add item in the tail
def append(self, coef, exp):
node = Node(coef, exp)
if self.__head == None:
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
def addl(l1, l2):
p1 = l1.gethead()
p2 = l2.gethead()
l3 = List()
while (p1 is not None) & (p2 is not None):
if (p1.exp > p2.exp):
l3.append(p1.coef, p1.exp)
p1 = p1.next
elif (p1.exp < p2.exp):
l3.append(p2.coef, p2.exp)
p2 = p2.next
else:
if (p1.coef + p2.coef == 0):
p1 = p1.next
p2 = p2.next
else:
l3.append(p2.coef + p1.coef, p1.exp)
p2 = p2.next
p1 = p1.next
while p1 is not None:
l3.append(p1.coef, p1.exp)
p1 = p1.next
while p2 is not None:
l3.append(p2.coef, p2.exp)
p2 = p2.next
if l3.gethead() == None:
l3.append(0, 0)
return l3
def mull(l1, l2):
p1 = l1.gethead()
p2 = l2.gethead()
l3 = List()
l4 = List()
if (p1 is not None) & (p2 is not None):
while p1 is not None:
while p2 is not None:
l4.append(p1.coef * p2.coef, p1.exp + p2.exp)
p2 = p2.next
l3 = addl(l3, l4)
l4 = List()
p2 = l2.gethead()
p1 = p1.next
else:
l3.append(0, 0)
return l3
def L2l(L):
l = List()
L.pop(0)
for i in range(0, len(L), 2):
l.append(L[i], L[i + 1])
return l
l1 = L2l(L1)
l2 = L2l(L2)
l3 = List()
l3 = mull(l1, l2)
l3.travel()
print("")
l3 = List()
l3 = addl(l1, l2)
l3.travel()
来源:https://www.cnblogs.com/nickchen121/p/11518875.html
0
投稿
猜你喜欢
- golang中GOPATH的简单理解 1、为什么要配置GOPATH配置GOPATH的用意是为了方便项目的部署和构建,以及可以直接使用go g
- 一、工厂模式(Factory Pattern)工厂模式(Factory Pattern),提供了一种实例化(创建)对象的最佳方式。在工厂模式
- 根据代码中运行的结果来看,主要由以下几种:1. sum():将array中每个元素相加的结果2. axis对应的是维度的相加。比如:1、ax
- 演示:<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//
- Beautiful Soup使用时,一般可以通过指定对应的name和attrs去搜索,特定的名字和属性,以找到所需要的部分的html代码。但
- MySQL出错代码列表:1005:创建表失败1006:创建数据库失败1007:数据库已存在,创建数据库失败1008:数据库不存在,删除数据库
- 如下所示:import cv2import numpy as npbins = np.arange(256).reshape(256,1)d
- MySQL是一个小型关系型数据库管理系统,开发者为瑞典MySQLAB公司,在2008年1月16号被Sun公司收购。MySQL被广泛地应用在I
- <!doctype html><html><head><meta http-equiv
- 还是决定冠上ajax的头衔,毕竟很多人会用这个关键词搜索。虽然我认为这只是个炒作的概念,不过不得不承认ajax叫起来要方便多了。ajax的意
- NLTK 是使用 Python 教学以及实践计算语言学的极好工具。此外,计算语言学与人工 智能、语言/专门语言识别、翻译以及语法检查等领域关
- 关于 *args与**args的用法*args 和 **kwargs主要用于函数定义,你可以将不定数量的参数传递给某个函数。*args*ar
- 本文研究的主要是Python编程通过pandas将数据分割成时间跨度相等的数据块的相关内容,具体如下。先上数据,有如下dataframe格式
- 最近在使用Python的过程中,发现网上很少提到在使用post方式时,怎么传一个数组作为参数的示例,此处根据自己的实践经验,给出相关示例:单
- OL定义有序列表的时候,除非指定list-style-position:inside;,否则文字和前导符是有缩进的。但有的时候,OL定义的列
- 是的,我们知道:我们可以为border设置它的width,这个border的宽度可以是5px,可是10px,可以是20px,可以是随意数值。
- 如何在本地机器上创建缓存?用法到是很简单,只需先创建Stream对象的实例,然后开始写入数据即可: Dim str&n
- 省市级联这东西基本是网注一份,而且基本是全是js写的,js写唯一坏处就是JS无效时不可用,我所说的js无效包括不支持js,js加载未完成或者
- 基于微信开放的个人号接口python库itchat,实现对微信好友的获取,并对省份、性别、微信签名做数据分析。效果:直接上代码,建三个空文本
- 一、生成随机的测验试卷文件假如你是一位地理老师, 班上有 35 名学生, 你希望进行美国各州首府的一个小测验。不妙的是,班里有几个坏蛋, 你