一、題意理解

創(chuàng)新互聯(lián)主打移動網(wǎng)站、成都做網(wǎng)站、成都網(wǎng)站設(shè)計、網(wǎng)站改版、網(wǎng)絡(luò)推廣、網(wǎng)站維護、域名注冊、等互聯(lián)網(wǎng)信息服務(wù)，為各行業(yè)提供服務(wù)。在技術(shù)實力的保障下，我們?yōu)榭蛻舫兄Z穩(wěn)定，放心的服務(wù)，根據(jù)網(wǎng)站的內(nèi)容與功能再決定采用什么樣的設(shè)計。最后，要實現(xiàn)符合網(wǎng)站需求的內(nèi)容、功能與設(shè)計，我們還會規(guī)劃穩(wěn)定安全的技術(shù)方案做保障。

給定兩棵樹T1和T2。如果T1可以通過若干次左右孩子互換就變成T2，則我們稱兩棵樹是“同構(gòu)的”。現(xiàn)給定兩棵樹，請你判斷它們是否是同構(gòu)的。

輸入格式：輸入給出2棵二叉樹的信息：

先在一行中給出該樹的結(jié)點樹，隨后N行

第i行對應(yīng)編號第i個結(jié)點，給出該結(jié)點中存儲的字母、其左孩子結(jié)點的編號、右孩子結(jié)點的編號

如果孩子結(jié)點為空，則在相應(yīng)位置給出“-”

如下圖所示，有多種表示的方式，我們列出以下兩種：

二、求解思路

搜到一篇也是講這個的，但是那篇并沒有完全用到單向鏈表的方法，所以研究了一下，寫了一個是完全用單向鏈表的方法：

其實應(yīng)該有更優(yōu)雅的刪除整個單向列表的方法，比如頭設(shè)為none，可能會改進下？

# python語言實現(xiàn)

L1 = list(map(int, input().split()))
L2 = list(map(int, input().split()))


# 節(jié)點
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()

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

文章名稱：python樹的同構(gòu)學(xué)習(xí)筆記-創(chuàng)新互聯(lián)
文章路徑：http://weahome.cn/article/djehjs.html