পাইথনে দুটি বাইনারি গাছের পাতার ট্র্যাভার্সাল একই কিনা তা পরীক্ষা করুন

ধরুন আমাদের দুটি বাইনারি গাছ আছে। এই দুটি গাছের পাতার ট্র্যাভার্সাল একই কিনা তা আমাদের পরীক্ষা করতে হবে। আমরা জানি যে পাতার ট্র্যাভার্সাল হল বাম থেকে ডানে যাওয়া পাতার ক্রম।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে True কারণ উভয় গাছের বাম ট্রাভার্সাল সিকোয়েন্স একই, অর্থাৎ [5, 7, 8]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• s1 :=একটি নতুন তালিকা, s2 :=আরেকটি নতুন তালিকা
• s1-এ r1 এবং s2-এ r2 ঢোকান
• যদিও s1 এবং s2 খালি নয়, কর
  • যদি s1 খালি হয় বা s2 খালি হয়, তাহলে
    • মিথ্যে ফেরত দিন
  • r1_node :=s1 এর শেষ নোড, এবং এটি s1 থেকে মুছে দিন
  • যদিও r1_node null এর মত নয় এবং r1_node পাতা নয়, do
    • যদি r1_node এর রাইট null এর মত না হয়, তাহলে
      • s1-এর শেষে r1_node-এর ডানদিকে ঢোকান
    • যদি r1_node এর বাম অংশ null এর মত না হয়, তাহলে
      • s1-এর শেষে r1_node-এর বাম দিকে ঢোকান
      • r1_node :=s1 এর শেষ নোড, এবং এটি s1 থেকে মুছে দিন
  • r2_node :=s2 এর শেষ নোড, এবং এটি s2 থেকে মুছে দিন
  • যদিও r2_node নাল নয় এবং r2_node পাতা নয়, do
    • যদি r2_node-এর রাইট শূন্য না হয়, তাহলে
      • s2-এর শেষে r2_node-এর ডানদিকে ঢোকান
    • যদি r2_node এর বাম অংশ নাল না হয়, তাহলে
      • s2-এর শেষে r2_node-এর বাম দিকে ঢোকান
    • r2_node :=s2 এর শেষ নোড, এবং এটি s2 থেকে মুছে দিন
  • যদি r1_node নাল হয় এবং r2_node নাল না হয়, তাহলে
    • মিথ্যে ফেরত দিন
  • যদি r1_node নাল না হয় এবং r2_node নাল না হয়, তাহলে
    • মিথ্যে ফেরত দিন
  • যদি r1_node এবং r2_node উভয়ই শূন্য না হয়, তাহলে
    • যদি r1_node-এর মান r2_node-এর মানের সমান না হয়, তাহলে
      • মিথ্যে ফেরত দিন
• সত্য ফেরান

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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