Pythonで2つの二分木が完全に同じかどうかを判定するプログラム(構造と値の比較)

2つの二分木が与えられたとき、それらが構造と値の両方の観点で完全に一致しているかどうかを確認します。このような木のペアは「双子の木(twin trees)」と呼ばれることがあります。

たとえば、次のような入力があったとします。

この場合、最初のペアに対する出力は True になります。一方、2番目と3番目のペアは、それぞれ「値が異なる」ケースと「構造が異なる」ケースに該当するため、出力は False になります。

解決のアプローチ

この問題は、再帰的な手法を用いて解くことができます。具体的には、以下の手順に従います。

• solve() メソッドを定義し、2つのルートノードを受け取るようにします。
• root0 と root1 の両方が null(None)の場合 → True を返します。
• root0 または root1 のどちらか一方だけが null の場合 → False を返します。
• root0 の値と root1 の値が異なる場合 → False を返します。
• solve(root0の左部分木, root1の左部分木) と solve(root0の右部分木, root1の右部分木) がどちらも True を返すときのみ True を返し、そうでなければ False を返します。

ポイントは、まず「両方が空なら一致」「片方だけ空なら不一致」という終了条件を先に判定することで、null 参照エラーを防いでいる点です。

以下の実装例を見ると、より理解しやすくなります。

コード例

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

class Solution:
    def solve(self, root0, root1):
        if not root0 and not root1:
            return True
        if not root0 or not root1:
            return False
        if root0.val != root1.val:
            return False
        return self.solve(root0.left, root1.left) and self.solve(root0.right, root1.right)

ob = Solution()
root1 = TreeNode(10)
root1.left = TreeNode(5)
root1.right = TreeNode(15)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(8)

root2 = TreeNode(10)
root2.left = TreeNode(5)
root2.right = TreeNode(15)
root2.left.left = TreeNode(3)
root2.left.right = TreeNode(8)

print(ob.solve(root1, root2))

入力

root1 = TreeNode(10)
root1.left = TreeNode(5)
root1.right = TreeNode(15)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(8)

root2 = TreeNode(10)
root2.left = TreeNode(5)
root2.right = TreeNode(15)
root2.left.left = TreeNode(3)
root2.left.right = TreeNode(8)

出力

True

計算量について

このアルゴリズムの時間計算量は O(n) です(n はノード数)。各ノードを一度だけ訪問して値を比較するため、非常に効率的に動作します。また、再帰の深さは木の高さに依存するため、極端に深い木を扱う場合はスタックオーバーフローに注意が必要ですが、通常の用途では問題ありません。