Chương trình tìm hiểu xem hai cây biểu thức có tương đương nhau hay không bằng cách sử dụng Python

Giả sử, chúng ta được cung cấp hai cây biểu thức. Chúng ta phải viết một chương trình kiểm tra hai cây biểu thức và xác định xem các cây biểu thức có tạo ra các giá trị giống nhau hay không. Hai cây biểu thức được cung cấp cho chúng tôi theo thứ tự và chúng tôi trả về giá trị True nếu chúng khớp nhau hoặc nếu không, chúng tôi trả về giá trị False.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là True.

Hai cây biểu thức đánh giá cùng một giá trị.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• Định nghĩa một hàm dfs (). Điều này sẽ lấy nút, dic

  • nếu nút trống, thì

    • trở lại

  • nếu bên trái của nút và bên phải của nút không trống, thì

    • dic [giá trị của nút]:=dic [giá trị của nút] + 1

  • dfs (bên trái của nút, dic)

  • dfs (bên phải của nút, dic)

• dic1:=một bản đồ mới chứa các giá trị số nguyên

• dic2:=một bản đồ mới chứa các giá trị số nguyên

• dfs (root1, dic1)

• dfs (root2, dic2)

• trả về True nếu dic1 giống với dic2.

Ví dụ

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))

Đầu vào

root1 = make_tree([1, '+', 2, '*', 3, '+', 4 ])
root2 = make_tree([2, '+', 1, '*', 4, '+', 3])

Đầu ra

True