【Python】二分木が別の木の部分木（サブツリー）かどうかを判定する方法

はじめに

プログラミングにおいて、ある二分木が別の二分木の部分木（サブツリー）であるかどうかを判定する処理は、よく登場する基本的な課題の一つです。この記事では、Pythonを使ってこの問題を効率的に解く方法を、具体的なコード例とともにわかりやすく解説します。

問題の概要

2つの二分木が与えられたとき、「2つ目の木が1つ目の木の部分木になっているか」を確認します。たとえば、次のような入力があった場合：

この場合、root2（値4を根とする木）は root1 の中にそのまま含まれているため、出力は True になります。

解法のアプローチ

この問題は再帰（recursion）を使うことでシンプルに解けます。判定用の関数 solve() を定義し、以下の手順で処理を進めます。

1. 両方のノードが null の場合：どちらも空なら構造的に一致しているので True を返します。
2. どちらか一方だけが null の場合：構造が異なるため False を返します。
3. ノードの値が一致している場合：左の子同士、右の子同士をそれぞれ再帰的に比較し、両方が一致すれば True を返します。
4. 値が一致しない場合：根の左側または右側の部分木の中に、対象の木が存在しないかを探索します。どちらかに見つかれば 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, root, target):
        # 両方のノードが null の場合は一致
        if root == None and target == None:
            return True
        # どちらか一方だけが null の場合は不一致
        if root == None or target == None:
            return False
        # 値が一致していれば、子ノードも再帰的に比較
        if root.val == target.val:
            return self.solve(root.left, target.left) and \
                   self.solve(root.right, target.right)
        else:
            # 一致しなければ、左右の部分木をさらに探索
            return self.solve(root.left, target) or \
                   self.solve(root.right, target)

ob = Solution()
root1 = TreeNode(6)
root1.left = TreeNode(4)
root1.right = TreeNode(10)
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)

root2 = TreeNode(4)
root2.left = TreeNode(3)
root2.right = TreeNode(5)

print(ob.solve(root1, root2))

入力データ

root1 = TreeNode(6)      # 根のノード
root1.left = TreeNode(4)   # 左側の部分木
root1.right = TreeNode(10) # 右側の部分木
root1.left.left = TreeNode(3)
root1.left.right = TreeNode(5)

root2 = TreeNode(4)        # 探索対象の木
root2.left = TreeNode(3)
root2.right = TreeNode(5)

出力結果

True

コードのポイント

• 再帰的な比較：値が一致した時点で、その配下の全ノードを再帰的に照合することで、部分木として完全に一致しているかを確認できます。
• nullチェックの順序が重要：まず「両方が null」のケースを先に判定し、その後に「片方だけ null」のケースを判定することで、正確に構造の一致・不一致を判別できます。
• 計算量：最悪の場合、各ノードに対して部分木との照合を行うため、時間計算量は O(n × m)（n は根の木のノード数、m は対象の木のノード数）となります。

まとめ

このように、再帰を使ったシンプルなロジックで、ある二分木が別の二分木の部分木であるかどうかを判定できます。二分木の操作は面接や競技プログラミングでも頻出のテーマなので、このパターンをぜひマスターしておきましょう。