মান লাগিয়ে, আমাদের দুটি এক্সপ্রেশন ট্রি দেওয়া আছে। আমাদের একটি প্রোগ্রাম লিখতে হবে যা দুটি এক্সপ্রেশন ট্রি চেক করে এবং নির্ধারণ করে যে এক্সপ্রেশন ট্রি দুটি একই মান জেনারেট করে কিনা। দুটি এক্সপ্রেশন ট্রি ইন-অর্ডার ম্যানারে দেওয়া থাকে এবং আমরা True রিটার্ন করব যদি সেগুলো মিলে যায়, অন্যথায় False।
যেমন, ইনপুট যদি এমন হয়:
তবে আউটপুট হবে True।
দুটি এক্সপ্রেশন ট্রি একই মান ইভ্যালুয়েট করে।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- একটি ফাংশন dfs() ডিফাইন করুন। এটি node, dic নেবে:
- যদি node খালি হয়, তবে রিটার্ন করুন
- যদি node.left এবং node.right খালি না হয়, তবে dic[node.val] := dic[node.val] + 1
- dfs(node.left, dic)
- dfs(node.right, dic)
- dic1 := ইন্টিজার ভ্যালু ধারণকারী একটি নতুন ম্যাপ
- dic2 := ইন্টিজার ভ্যালু ধারণকারী একটি নতুন ম্যাপ
- dfs(root1, dic1)
- dfs(root2, dic2)
- True রিটার্ন করুন যদি dic1 == dic2
উদাহরণ
import collections
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def solve(root1, root2):
dic1 = collections.defaultdict(int)
dic2 = collections.defaultdict(int)
def dfs(node, dic):
if not node:
return
if not node.left and not node.right:
dic[node.val] += 1
dfs(node.left, dic)
dfs(node.right, dic)
dfs(root1, dic1)
dfs(root2, dic2)
return dic1 == dic2
root1 = make_tree([1, '+', 2, '*', 3, '+', 4 ])
root2 = make_tree([2, '+', 1, '*', 4, '+', 3])
print(solve(root1, root2))
ইনপুট
root1 = make_tree([1, '+', 2, '*', 3, '+', 4 ]) root2 = make_tree([2, '+', 1, '*', 4, '+', 3])
আউটপুট
True
