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

মান লিজিয়ে আমাদের দুটি বাইনারি ট্রি (binary tree) আছে। আমাদের যাচাই করতে হবে এই দুটি ট্রির লীফ ট্রাভার্সেল (leaf traversal) একই কিনা। আমরা জানি লীফ ট্রাভার্সেল হল বাম থেকে ডানে লীফ নোডগুলোর ট্রাভার্সেল সিকোয়েন্স।

যেমন, ইনপুট যদি:

তবে আউটপুট হবে True কারণ দুটি ট্রির লীফ ট্রাভার্সেল সিকোয়েন্স একই, যা হল [5, 7, 8]।

সমাধানের ধাপসমূহ

s1 := একটি নতুন লিস্ট, s2 := আরেকটি নতুন লিস্ট
r1 s1-এ এবং r2 s2-এ ইনসার্ট করুন
যখন s1 এবং s2 খালি নয়, করুন:
- যদি s1 খালি হয় অথবা s2 খালি হয়, তবে:
  - False রিটার্ন করুন
- r1_node := s1-এর লাস্ট নোড, এবং s1-এ থেকে ডিলিট করুন
- যখন r1_node নাল নয় এবং r1_node লীফ নয়, করুন:
  - যদি r1_node-এর রাইট নাল নয়, তবে:
    - r1_node-এর রাইট s1-এর শেষে ইনসার্ট করুন
  - যদি r1_node-এর লেফট নাল নয়, তবে:
    - r1_node-এর লেফট s1-এর শেষে ইনসার্ট করুন
    - r1_node := s1-এর লাস্ট নোড, এবং s1-এ থেকে ডিলিট করুন
- r2_node := s2-এর লাস্ট নোড, এবং s2-এ থেকে ডিলিট করুন
- যখন r2_node নাল নয় এবং r2_node লীফ নয়, করুন:
  - যদি r2_node-এর রাইট নাল নয়, তবে:
    - r2_node-এর রাইট s2-এর শেষে ইনসার্ট করুন
  - যদি r2_node-এর লেফট নাল নয়, তবে:
    - r2_node-এর লেফট s2-এর শেষে ইনসার্ট করুন
  - r2_node := s2-এর লাস্ট নোড, এবং s2-এ থেকে ডিলিট করুন
- যদি r1_node নাল হয় এবং r2_node নাল নয়, তবে:
  - False রিটার্ন করুন
- যদি r1_node নাল নয় এবং r2_node নাল হয়, তবে:
  - False রিটার্ন করুন
- যদি r1_node এবং r2_node দুটোই নাল নয়, তবে:
  - যদি r1_node-এর ভ্যালু r2_node-এর ভ্যালু সমান না হয়, তবে:
    - False রিটার্ন করুন
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