โปรแกรมตรวจสอบต้นไม้สองต้นสามารถเกิดขึ้นได้โดยการสลับโหนดหรือไม่ใน Python

สมมติว่าเรามีต้นไม้สองต้น เราต้องตรวจสอบว่าเราสามารถแปลงต้นไม้แรกเป็นต้นไม้ที่สองได้ด้วยการสลับทรีย่อยทางซ้ายและขวาของโหนดจำนวนเท่าใดก็ได้

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

แล้วผลลัพธ์จะเป็น True

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

• que1 :=คิวที่มี root0 เริ่มแรก

• que2 :=คิวที่มีรูท 1 เริ่มแรก

• ในขณะที่ que1 และ que2 ไม่ว่างเปล่าให้ทำ

  • temp1 :=รายการใหม่ temp2 :=รายการใหม่

  • ค่าที่ 1 :=รายการใหม่ ค่า2 :=รายการใหม่

  • ถ้า que1 และ que2 มีจำนวนองค์ประกอบต่างกัน ดังนั้น

    • คืนค่าเท็จ

  • สำหรับฉันในช่วง 0 ถึงขนาด que1 − 1 ทำ

    • แทรกค่าของ que1[i] ที่ส่วนท้ายของค่า1

    • แทรกค่าของ que2[i] ที่ส่วนท้ายของค่า2

    • หากสิทธิ์ของ que1[i] ไม่เป็นโมฆะ

      • แทรกด้านขวาของ que1[i] ที่ส่วนท้ายของ temp1

    • หากทางซ้ายของ que1[i] ไม่เป็นโมฆะ

      • แทรกด้านซ้ายของ que1[i] ที่ส่วนท้ายของ temp1

    • หากสิทธิ์ของ que2[i] ไม่เป็นโมฆะ

      • แทรกด้านขวาของ que2[i] ที่ส่วนท้ายของ temp2

    • หากทางซ้ายของ que2[i] ไม่เป็นโมฆะ

      • แทรกด้านซ้ายของ que2[i] ที่ส่วนท้ายของ temp2

  • ถ้าค่าที่ 1 ไม่เหมือนกับค่าที่ 2 แล้ว

    • ถ้าค่าที่ 1 ไม่เหมือนกับค่าที่ 2 ในลำดับที่กลับกัน

      • คืนค่าเท็จ

  • que1 :=temp1, que2 :=temp2

• คืนค่า True

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

ตัวอย่าง

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root0, root1):
      que1 = [root0]
      que2 = [root1]
      while que1 and que2:
         temp1 = []
         temp2 = []
         values1 = []
         values2 = []
         if len(que1) != len(que2):
            return False
         for i in range(len(que1)):
            values1.append(que1[i].val)
            values2.append(que2[i].val)
         if que1[i].right:
            temp1.append(que1[i].right)
         if que1[i].left:
            temp1.append(que1[i].left)
         if que2[i].right:
            temp2.append(que2[i].right)
         if que2[i].left:
            temp2.append(que2[i].left)
      if values1 != values2:
         if values1 != values2[::-1]:
            return False
      que1 = temp1
      que2 = temp2
   return True
ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
root1 = TreeNode(2)
root1.left = TreeNode(4)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)
print(ob.solve(root, root1))

อินพุต

root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)
root1 = TreeNode(2)
root1.left = TreeNode(4)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)

ผลลัพธ์

True