Pythonで2つの二分木の全レベルがアナグラムかどうかを判定する方法

問題概要

2つの二分木が与えられたとき、片方の木の各レベルに含まれる値の集合が、もう片方の木の同じレベルの値のアナグラム（並べ替え）になっているかどうかを判定します。すべてのレベルがアナグラムであれば True を、そうでなければ False を返します。

例えば、次のような入力が与えられた場合を考えてみましょう。

この場合、出力は True になります。

解法のアプローチ

この問題は、幅優先探索（BFS）を応用して解くことができます。各レベルごとにノードの値を収集し、ソートした上で比較するのがポイントです。手順は以下の通りです。

1. tree_1 を1つ目の木のルートノード、tree_2 を2つ目の木のルートノードとします。
2. tree_1 と tree_2 がどちらも null の場合は True を返します。
3. tree_1 または tree_2 のどちらか一方だけが null の場合は False を返します。
4. 2つのキュー queue1 と queue2 を作成し、それぞれに tree_1、tree_2 を追加します。
5. 以下の処理を繰り返します。
   • size1 を queue1 のサイズ、size2 を queue2 のサイズとします。
   • size1 と size2 が異なる場合は False を返します（同じレベルのノード数が一致しないため、アナグラムになり得ません）。
   • size1 が 0 の場合はループを抜けます。
   • 現在のレベルの値を格納するためのリスト curr_level1 と curr_level2 を作成します。
   • size1 > 0 の間、各キューから先頭のノードを取り出し、存在する子ノードをキューの末尾に追加しながら、現在のノードの値を curr_level リストに記録していきます。
   • curr_level1 と curr_level2 をそれぞれソートし、内容が一致しない場合は False を返します。
6. すべてのレベルの比較が完了すれば True を返します。

実装例

理解を深めるために、以下のPythonによる実装を見てみましょう。

def make_tree(elements):
    tree = tree_node(elements[0])
    for element in elements[1:]:
        insert_value(tree, element)
    return tree

def insert_value(temp, value):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if value is not None:
                temp.left = tree_node(value)
            else:
                temp.left = tree_node(0)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if value is not None:
                temp.right = tree_node(value)
            else:
                temp.right = tree_node(0)
            break
        else:
            que.append(temp.right)

class tree_node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def solve(tree_1, tree_2):
    if (tree_1 == None and tree_2 == None):
        return True
    if (tree_1 == None or tree_2 == None):
        return False
    queue1 = []
    queue2 = []
    queue1.append(tree_1)
    queue2.append(tree_2)
    while (1):
        size1 = len(queue1)
        size2 = len(queue2)
        if (size1 != size2):
            return False
        if (size1 == 0):
            break
        curr_level1 = []
        curr_level2 = []
        while (size1 > 0):
            node1 = queue1[0]
            queue1.pop(0)
            if (node1.left != None):
                queue1.append(node1.left)
            if (node1.right != None):
                queue1.append(node1.right)
            size1 -= 1
            node2 = queue2[0]
            queue2.pop(0)
            if (node2.left != None):
                queue2.append(node2.left)
            if (node2.right != None):
                queue2.append(node2.right)
            curr_level1.append(node1.value)
            curr_level2.append(node2.value)
        curr_level1.sort()
        curr_level2.sort()
        if (curr_level1 != curr_level2):
            return False
    return True

tree_1 = make_tree([5, 6, 7, 9, 8])
tree_2 = make_tree([5, 7, 6, 8, 9])
print(solve(tree_1, tree_2))

入力

[5, 6, 7, 9, 8], [5, 7, 6, 8, 9]

出力

True

計算量について

このアルゴリズムでは、各ノードをちょうど1回ずつ処理するため、走査自体の計算量は O(n) です。ただし、各レベルのリストをソートする必要があるため、全体の時間計算量は最悪の場合 O(n log n) となります。空間計算量は、キューとレベル用リストの合計で O(n) です。