โปรแกรมตรวจสอบ Equivalence ของ Expression Tree 2 ตัวด้วย Python

Expression tree 2 ตัวเทียบเท่ากันถ้าผลลัพธ์เท่ากัน สำหรับ operator แบบ commutative (+, *) สามารถนับความถี่ของ operand (leaf nodes) ได้: ถ้าทั้งสอง tree มี leaf nodes เหมือนกัน (นับรวมความถี่) ถือว่าเทียบเท่า ใช้ DFS นับ leaf values ใน dictionary แล้วเปรียบเทียบ dict

ขั้นตอนการทำงาน

1. DFS ทั้งสอง tree นับความถี่ของ leaf node values (operands)
2. Operator nodes (+, -, *, /) ไม่นับ เพราะคำสั่งนี้สมมติ commutative
3. เปรียบเทียบ dictionary ทั้งสอง ถ้าเท่ากัน return True

ตัวอย่างโค้ด

import collections

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = 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:  # leaf node
            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))  # Output: True

อินพุต/เอาต์พุต

Input: root1=[1,+,2,*,3,+,4], root2=[2,+,1,*,4,+,3]
Output: True