Pythonで左右の部分木が同一となる最大の部分木を見つける方法

問題の概要

二分木が与えられたとき、左の部分木と右の部分木が完全に一致している最大の部分木を見つけることを考えます。望ましい計算量は O(n) です。

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

この場合、出力は次のようになります。

解法のアプローチ

この問題を解くためには、木をボトムアップ（下から上へ）に走査し、各ノードについて「そのノードを根とする部分木の構造を表す文字列（エンコード）」を作成します。そして、左部分木のエンコードと右部分木のエンコードが一致していれば、そのノードは「左右が同一の部分木」の根であると判断できます。

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

1. solve() 関数を定義します。引数は root（現在のノード）、encode（エンコード文字列を格納するリスト）、maxSize（最大サイズを格納するリスト）、maxNode（該当ノードを格納するリスト）です。
2. root が None の場合は 0 を返します。
3. left_list と right_list を空文字列を持つリストとして初期化します。
4. ls := solve(root.left, left_list, maxSize, maxNode) で左部分木を再帰的に処理します。
5. rs := solve(root.right, right_list, maxSize, maxNode) で右部分木を再帰的に処理します。
6. size := ls + rs + 1 として、現在の部分木のサイズを計算します。
7. left_list[0] と right_list[0] が一致している場合、つまり左右の部分木が同一である場合は、size が maxSize[0] より大きければ maxSize[0] と maxNode[0] を更新します。
8. encode[0] に「| 左部分木のエンコード | 現在のノードの値 | 右部分木のエンコード |」という形式で連結していきます。このエンコードによって、親ノードでは子孫の構造全体を比較できるようになります。
9. 最後に size を返します。

メインの処理では以下を行います。

• maximum := [0]、encode := [""]、maxNode := [None] を初期化します。
• solve(node, encode, maximum, maxNode) を呼び出します。
• maximum を返します。

実装例

それでは、実際の Python コードを見てみましょう。

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

def solve(root, encode, maxSize, maxNode):
    if (root == None):
        return 0
    left_list = [""]
    right_list = [""]
    ls = solve(root.left, left_list, maxSize, maxNode)
    rs = solve(root.right, right_list, maxSize, maxNode)
    size = ls + rs + 1
    if (left_list[0] == right_list[0]):
        if (size > maxSize[0]):
            maxSize[0] = size
            maxNode[0] = root
    encode[0] = encode[0] + "|" + left_list[0] + "|"
    encode[0] = encode[0] + "|" + str(root.data) + "|"
    encode[0] = encode[0] + "|" + right_list[0] + "|"

    return size

def largestSubtree(node, maxNode):
    maximum = [0]
    encode = [""]
    solve(node, encode, maximum, maxNode)
    return maximum

root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)

maxNode = [None]
maximum = largestSubtree(root, maxNode)
print("Root of largest sub-tree", maxNode[0].data)
print("and its size is", maximum)

入力

root = TreeNode(55)
root.left = TreeNode(15)
root.right = TreeNode(70)
root.left.left = TreeNode(10)
root.left.right = TreeNode(25)
root.right.left = TreeNode(75)
root.right.left.left = TreeNode(65)
root.right.left.right = TreeNode(80)
root.right.right = TreeNode(75)
root.right.right.left = TreeNode(65)
root.right.right.right = TreeNode(80)

出力

Root of largest sub-tree 70
and its size is [7]

コードの解説

この例では、値 70 を根とするノードに注目してください。その左の子は 75（さらにその下に 65 と 80）、右の子も 75（その下に 65 と 80）となっており、左右の部分木が完全に一致しています。この部分木のサイズは 7 ノードなので、これが答えとなります。

ポイント解説

• リストを使った参照渡し： Python の整数や文字列はイミュータブル（変更不可）なため、再帰の中で値を共有するにはリストなどのミュータブルなオブジェクトを使うのが定石です。ここでは maxSize、maxNode、encode をそれぞれ要素 1 つのリストとして渡しています。
• エンコードによる構造比較： 各ノードのサブツリーを「| 値 |」の形式で文字列化していくことで、単なる値の一致ではなく、構造を含めた完全な一致を判定できます。
• 計算量： 各ノードを一度だけ訪問するため、時間計算量は O(n) です。ただし、エンコード文字列の連結により、最悪の場合 O(n²) のメモリ・時間がかかる可能性がある点には注意が必要です。より厳密に O(n) にしたい場合は、ハッシュ化や部分木 ID の利用が有効です。