Pythonで2つの式木（式ツリー）が同じ値に評価されるか判定する方法

問題の概要

2つの式木（expression tree）が与えられ、それぞれが同じ値に評価されるかどうかを判定するプログラムを作成します。式木はリスト形式で与えられ、2つの式木の評価結果が一致していれば True を、一致していなければ False を返します。

例えば、下図のような2つの式木が与えられた場合を考えてみましょう。

このとき出力は True となります。2つの式木が同じ値に評価されるためです。

解決のためのステップ

この問題は、深さ優先探索（DFS）を使って各木を走査し、葉ノードの値を出現回数として記録したうえで、その辞書同士を比較することで解けます。手順は以下のとおりです。

1. dfs(node, dic) 関数を定義します。
   • node が空（None）の場合は何もせずに return します。
   • node の左右どちらにも子がない（葉ノードである）場合は、dic[node.val] のカウントを 1 増やします。
   • dfs(node.left, dic) と dfs(node.right, dic) を順に再帰呼び出しします。
2. 整数値を格納する新しいマップ（defaultdict）として dic1 と dic2 を用意します。
3. dfs(root1, dic1) と dfs(root2, dic2) を実行します。
4. dic1 と dic2 が完全に一致すれば True を返します。

実装例（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

アルゴリズムのポイント

dfs 関数は各木を再帰的にたどり、子を持たないノード（葉）の値だけを辞書に記録します。こうして得られた2つの辞書を比較すれば、2つの式木が同じ構成要素を持っているかどうかを効率的に判定できます。計算量は各木を一度ずつ訪問するだけなので O(n) です。

なお、この手法は「葉の値の組み合わせが同一か」を比較するアプローチです。演算子の種類や結合順序まで含めて厳密に評価値を検証したい場合は、木そのものを再帰的に評価して結果を比較する必要がある点に注意してください。