Pythonで左右の部分木の入れ替えにより2つの二分木を一致させられるか判定する方法

問題の概要

2つの二分木が与えられたとき、任意のノードについて左部分木と右部分木を何度でも入れ替えてよいと仮定します。この操作を繰り返すことで、1つ目の木を2つ目の木とまったく同じ形に変換できるかどうかを判定するのが、この記事で扱う問題です。

例えば、次のような2つの木が入力として与えられた場合、左右の入れ替えによって一致させられるため、出力は True になります。

解決のアプローチ

この問題は、幅優先探索（BFS）の考え方を使い、木をレベル（深さ）ごとに処理しながらノードの値を比較することで解けます。左右の入れ替えによって同じレベル内の値の並び順は反転し得るため、「順方向」または「逆方向」のどちらかで一致していればよいことになります。

具体的な手順は以下の通りです。

• キュー que1 に root0 を、キュー que2 に root1 を入れて初期化します。
• que1 と que2 のどちらも空でない限り、次の処理を繰り返します。
  • 次のレベル用の一時リスト temp1・temp2 と、現在のレベルの値を集めるリスト values1・values2 を用意します。
  • 2つのキューの要素数が異なる場合は、木の構造が対応していないため False を返します。
  • 各キューの要素について、ノードの値を values1・values2 に追加します。また、子ノードは「右 → 左」の順で temp1・temp2 に登録します。これは、左右の入れ替えによって並びが反転することを考慮するためです。
  • values1 と values2 が一致せず、さらに values1 を逆順にしたものとも一致しない場合は False を返します。
  • que1・que2 をそれぞれ temp1・temp2 で更新し、次のレベルへ進みます。
• すべてのレベルの比較を通過できれば True を返します。

Pythonでの実装例

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right


class Solution:
    def solve(self, root0, root1):
        que1 = [root0]
        que2 = [root1]
        while que1 and que2:
            temp1 = []
            temp2 = []
            values1 = []
            values2 = []
            if len(que1) != len(que2):
                return False
            for i in range(len(que1)):
                values1.append(que1[i].val)
                values2.append(que2[i].val)
                if que1[i].right:
                    temp1.append(que1[i].right)
                if que1[i].left:
                    temp1.append(que1[i].left)
                if que2[i].right:
                    temp2.append(que2[i].right)
                if que2[i].left:
                    temp2.append(que2[i].left)
            if values1 != values2:
                if values1 != values2[::-1]:
                    return False
            que1 = temp1
            que2 = temp2
        return True


ob = Solution()
root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)

root1 = TreeNode(2)
root1.left = TreeNode(4)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)

print(ob.solve(root, root1))

入力

root = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(3)
root.right.right = TreeNode(5)

root1 = TreeNode(2)
root1.left = TreeNode(4)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)

出力

True

結果の解説

1つ目の木では、根ノード 2 の右側に 4 がぶら下がり、その下に 3（左）と 5（右）が配置されています。一方、2つ目の木では 4 が根の左側に移っていますが、4 の子の並び（3 が左、5 が右）は変わっていません。

つまり、根ノード 2 の左右の部分木を一度入れ替えるだけで2つの木は完全に一致するため、プログラムは True を返します。このように、レベルごとの値の並びが順方向・逆方向のいずれかで一致しているかを確認するだけで、左右の入れ替えによる変換の可否を効率的に判定できます。