यह पता लगाने के लिए कार्यक्रम कि क्या दो अभिव्यक्ति पेड़ पायथन का उपयोग करने के बराबर हैं

मान लीजिए, हमें दो व्यंजक वृक्ष दिए गए हैं। हमें एक प्रोग्राम लिखना है जो दो एक्सप्रेशन ट्री की जांच करता है और यह निर्धारित करता है कि एक्सप्रेशन ट्री समान मान उत्पन्न करते हैं या नहीं। दो एक्सप्रेशन ट्री हमें इन-ऑर्डर तरीके से प्रदान किए जाते हैं और यदि वे मेल खाते हैं तो हम एक ट्रू वैल्यू लौटाते हैं, या फिर हम एक गलत वैल्यू लौटाते हैं।

तो, अगर इनपुट पसंद है

तो आउटपुट ट्रू होगा।

दो व्यंजक वृक्ष एक ही मान का मूल्यांकन करते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• फ़ंक्शन को परिभाषित करें dfs() । यह नोड लेगा, dic

  • अगर नोड खाली है, तो

    • वापसी

  • यदि नोड का बायां और नोड का दायां खाली नहीं है, तो

    • dic[नोड का मान] :=dic[नोड का मान] + 1

  • dfs (नोड के बाएँ, dic)

  • dfs (नोड का दायां, dic)

• dic1 :=पूर्णांक मानों वाला एक नया मानचित्र

• dic2 :=पूर्णांक मानों वाला एक नया मानचित्र

• dfs(root1, dic1)

• dfs(root2, dic2)

• यदि 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