ตรวจสอบว่าทุกระดับของต้นไม้สองต้นเป็นแอนนาแกรมหรือไม่ใน Python

สมมติว่าเรามีต้นไม้ไบนารีสองต้น เราต้องตรวจสอบว่าแต่ละระดับของไบนารีทรีเป็นแอนนาแกรมของระดับเดียวกันของไบนารีทรีอื่นหรือไม่ เราจะคืนค่า True หากเป็นแอนนาแกรม มิฉะนั้น เราจะคืนค่าเป็นเท็จ

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• tree_1 คือโหนดรากของต้นไม้ต้นแรก และ tree_2 คือโหนดรากของต้นไม้ต้นที่สอง
• ถ้า tree_1 เหมือนกับ null และ tree_2 เหมือนกับ null ดังนั้น
  • คืนค่า True
• ถ้า tree_1 เหมือนกับ null หรือ tree_2 เหมือนกับ null ดังนั้น
  • คืนค่าเท็จ
• queue1 :=คิวใหม่
• queue2 :=คิวใหม่
• แทรก tree_1 ที่ท้ายคิว1
• แทรก tree_2 ที่ท้ายคิว2
• ในขณะที่ 1 ไม่ใช่ศูนย์ ให้ทำ
  • size1 :=ขนาดของคิว1
  • size2 :=ขนาดของคิว2
  • ถ้า size1 ไม่เหมือนกับ size2 แล้ว
    • คืนค่าเท็จ
  • ถ้า size1 เท่ากับ 0 แล้ว
    • ออกมาจากวงจร
  • curr_level1 :=รายการใหม่
  • curr_level2 :=รายการใหม่
  • ในขณะที่ size1> 0 ทำ
    • node1 :=องค์ประกอบแรกของคิว1
    • ลบองค์ประกอบแรกออกจาก Queue1
    • หากด้านซ้ายของ node1 ไม่เหมือนกับ null ดังนั้น
      • แทรกด้านซ้ายของ node1 ที่ท้ายคิว1
    • ถ้าด้านขวาของ node1 ไม่เหมือนกับ null แล้ว
      • แทรกด้านขวาของ node1 ที่ท้ายคิว1
    • size1 :=size1 - 1
    • node2 :=องค์ประกอบแรกของคิว2
    • ลบองค์ประกอบแรกออกจาก Queue2
    • ถ้าด้านซ้ายของ node2 ไม่เหมือนกับ null แล้ว
      • แทรกด้านซ้ายของ node2 ที่ท้ายคิว2
    • ถ้าด้านขวาของ node2 ไม่เหมือนกับ null แล้ว
      • แทรกด้านขวาของ node2 ที่ท้ายคิว2
    • ใส่ค่าของ node1 ที่ส่วนท้ายของ curr_level1
    • ใส่ค่าของ node2 ที่ส่วนท้ายของ curr_level2
  • เรียงลำดับรายการ curr_level1
  • เรียงลำดับรายการ curr_level2
  • ถ้า curr_level1 ไม่เหมือนกับ curr_level2 แล้ว
    • คืนค่าเท็จ
• คืนค่า True

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def make_tree(elements):
   tree = tree_node(elements[0])
   for element in elements[1:]:
      insert_value(tree, element)
   return tree
def insert_value(temp,value):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if value is not None:
            temp.left = tree_node(value)
         else:
            temp.left = tree_node(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if value is not None:
            temp.right = tree_node(value)
         else:
            temp.right = tree_node(0)
         break
      else:
         que.append(temp.right)
class tree_node:
   def __init__(self, value):
      self.value = value
      self.left = None
      self.right = None
def solve(tree_1, tree_2) :
   if (tree_1 == None and tree_2 == None) :
      return True
   if (tree_1 == None or tree_2 == None) :
      return False
   queue1 = []
   queue2 = []
   queue1.append(tree_1)
   queue2.append(tree_2)
   while (1) :
      size1 = len(queue1)
      size2 = len(queue2)
      if (size1 != size2):
         return False
      if (size1 == 0):
         break
      curr_level1 = []
      curr_level2 = []
      while (size1 > 0):
         node1 = queue1[0]
         queue1.pop(0)
         if (node1.left != None) :
            queue1.append(node1.left)
         if (node1.right != None) :
            queue1.append(node1.right)
         size1 -= 1
         node2 = queue2[0]
         queue2.pop(0)
         if (node2.left != None) :
            queue2.append(node2.left)
         if (node2.right != None) :
            queue2.append(node2.right)
         curr_level1.append(node1.value)
         curr_level2.append(node2.value)
      curr_level1.sort()
      curr_level2.sort()
      if (curr_level1 != curr_level2) :
         return False
   return True
tree_1 = make_tree([5, 6, 7, 9, 8])
tree_2 = make_tree([5, 7, 6, 8, 9])
print(solve(tree_1, tree_2))

อินพุต

[5, 6, 7, 9, 8], [5, 7, 6, 8, 9]

ผลลัพธ์

True