Python을 활용해 두 개의 표현식 트리가 같은 값을 갖는지 확인하는 프로그램

문제 개요

두 개의 표현식 트리(expression tree)가 주어졌을 때, 이 두 트리가 서로 같은 결과값을 만들어 내는지 판별하는 프로그램을 작성해야 합니다. 두 표현식 트리는 중위 순회(in-order) 형태로 제공되며, 값이 일치하면 True, 그렇지 않으면 False를 반환하면 됩니다.

예를 들어 입력이 아래와 같다면,

출력은 True입니다. 두 표현식 트리가 동일한 값으로 평가되기 때문입니다.

해결 접근 방법

이 문제는 깊이 우선 탐색(DFS)을 활용해 해결할 수 있습니다. 핵심 아이디어는 각 트리에서 피연산자 역할을 하는 리프 노드들의 값을 세어, 두 트리의 리프 노드 구성이 완전히 동일한지 비교하는 것입니다. 단계별로 살펴보면 다음과 같습니다.

• dfs() 함수 정의 — 매개변수로 node와 dic을 받습니다.

  • node가 비어 있으면(None) 그대로 반환합니다.

  • node의 왼쪽 자식과 오른쪽 자식이 모두 없다면, 즉 리프 노드라면 dic[node.val] 값을 1 증가시킵니다.

  • dfs(node.left, dic)을 재귀적으로 호출합니다.

  • dfs(node.right, dic)을 재귀적으로 호출합니다.

• 정수 값을 저장하는 새로운 딕셔너리 dic1을 생성합니다.

• 같은 방식으로 dic2를 생성합니다.

• dfs(root1, dic1)과 dfs(root2, dic2)를 호출해 각 트리의 리프 노드를 카운트합니다.

• dic1과 dic2가 완전히 같으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

이 방식의 시간 복잡도는 트리의 노드 수를 n이라 할 때 O(n)이며, 공간 복잡도 또한 O(n)입니다.

예제 코드

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

동작 원리 설명

첫 번째 트리의 리프 노드는 *, 3, +, 4이고, 두 번째 트리의 리프 노드는 *, 4, +, 3입니다. 연산자와 피연산자의 등장 횟수가 두 트리에서 완전히 동일하므로 두 딕셔너리가 일치하게 되고, 최종적으로 True가 출력됩니다. 이처럼 DFS로 리프 노드만 추출해 빈도를 비교하면 트리의 구조가 달라도 평가 결과가 같은지 손쉽게 판별할 수 있습니다.