使用Python编写程序以查找两个表达式树是否相等

假设我们提供两个表达式树。我们必须编写一个程序来检查这两个表达式树，并确定它们生成的值是否相似。我们以in-order方式提供了两个表达式树，如果它们匹配，则返回True值，否则返回False值。

因此，如果输入如下：

那么输出将是True。

这两个表达式树的计算结果相同。

为了解决这个问题，我们将按照以下步骤进行：

• 定义一个函数dfs()。这将使用节点和字典作为参数。
  • 如果节点为空，则：
    • 返回
  • 如果节点的左节点和右节点不为空，则：
    • 将节点值的字典dic[value of node]加1
  • dfs(节点的左子节点，dic)
  • dfs(节点的右子节点，dic)
• 创建一个包含整数值的新字典dic1
• 创建一个包含整数值的新字典dic2
• dfs(root1, dic1)
• dfs(root2, dic2)
• 如果dic1等于dic2，则返回True。

  更多Python相关文章，请阅读：Python 教程

示例

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