ตรวจสอบว่าการข้ามใบของต้นไม้ไบนารีสองต้นเหมือนกันใน Python . หรือไม่

สมมติว่าเรามีไบนารีทรีสองทรี เราต้องเช็คว่าใบผ่านของต้นไม้สองต้นนี้เหมือนกันหรือไม่ อย่างที่ทราบกันดีว่าการเลื่อนใบไม้เป็นลำดับของใบไม้ที่เคลื่อนจากซ้ายไปขวา

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

จากนั้นผลลัพธ์จะเป็น True เนื่องจากลำดับการข้ามทางซ้ายของต้นไม้ทั้งสองเหมือนกัน นั่นคือ [5, 7, 8]

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

• s1 :=รายการใหม่ s2 :=รายการใหม่อีกรายการ
• แทรก r1 ลงใน s1 และ r2 ลงใน s2
• ในขณะที่ s1 และ s2 ไม่ว่างเปล่า ให้ทำ
  • ถ้า s1 ว่างเปล่าหรือ s2 ว่างเปล่า ดังนั้น
    • คืนค่าเท็จ
  • r1_node :=โหนดสุดท้ายของ s1 และลบออกจาก s1
  • ในขณะที่ r1_node ไม่เหมือนกับ null และ r1_node ไม่ใช่ leaf ให้ทำ
    • หากสิทธิ์ของ r1_node ไม่เหมือนกับ null ดังนั้น
      • แทรกด้านขวาของ r1_node ที่ส่วนท้ายของ s1
    • หากทางซ้ายของ r1_node ไม่เหมือนกับ null ดังนั้น
      • แทรกด้านซ้ายของ r1_node ที่ส่วนท้ายของ s1
      • r1_node :=โหนดสุดท้ายของ s1 และลบออกจาก s1
  • r2_node :=โหนดสุดท้ายของ s2 และลบออกจาก s2
  • ในขณะที่ r2_node ไม่เป็น null และ r2_node ไม่ใช่ leaf ให้ทำ
    • หากสิทธิ์ของ r2_node ไม่เป็นโมฆะ
      • แทรกด้านขวาของ r2_node ที่ส่วนท้ายของ s2
    • หากทางซ้ายของ r2_node ไม่เป็นโมฆะ
      • แทรกด้านซ้ายของ r2_node ที่ส่วนท้ายของ s2
    • r2_node :=โหนดสุดท้ายของ s2 และลบออกจาก s2
  • ถ้า r1_node เป็น null และ r2_node ไม่เป็น null ดังนั้น
    • คืนค่าเท็จ
  • ถ้า r1_node ไม่เป็น null และ r2_node เป็น null ดังนั้น
    • คืนค่าเท็จ
  • ถ้า r1_node และ r2_node ทั้งคู่ไม่เป็นโมฆะ ดังนั้น
    • ถ้าค่าของ r1_node ไม่เหมือนกับค่าของ r2_node แล้ว
      • คืนค่าเท็จ
• คืนค่า True

ตัวอย่าง

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

class TreeNode:
   def __init__(self, x):
      self.val = x
      self.left = self.right = None
   def is_leaf(self):
      return self.left == None and self.right == None
def solve(r1, r2):
   s1 = []
   s2 = []
   s1.append(r1)
   s2.append(r2)
   while len(s1) != 0 or len(s2) != 0:
      if len(s1) == 0 or len(s2) == 0:
         return False
      r1_node = s1.pop(-1)
      while r1_node != None and not r1_node.is_leaf():
         if r1_node.right != None:
            s1.append(r1_node.right)
         if r1_node.left != None:
            s1.append(r1_node.left)
            r1_node = s1.pop(-1)
      r2_node = s2.pop(-1)
      while r2_node != None and not r2_node.is_leaf():
         if r2_node.right != None:
            s2.append(r2_node.right)
         if r2_node.left != None:
            s2.append(r2_node.left)
         r2_node = s2.pop(-1)
      if r1_node == None and r2_node != None:
         return False
      if r1_node != None and r2_node == None:
   return False
if r1_node != None and r2_node != None:
if r1_node.val != r2_node.val:
return False
return True
root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)
print(solve(root1, root2))

อินพุต

root1 = TreeNode(2)
root1.left = TreeNode(3)
root1.right = TreeNode(4)
root1.left.left = TreeNode(5)
root1.right.left = TreeNode(7)
root1.right.right = TreeNode(8)
root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)

ผลลัพธ์

True