Pythonで2つの二分木の葉の走査（リーフトラバーサル）が同じかどうかを判定する方法

問題概要

2つの二分木が与えられたとき、それらの「葉の走査（リーフトラバーサル）」が同じかどうかを判定する問題を考えてみましょう。葉の走査とは、木を左から右へと辿ったときに現れる葉ノードの値の並び順のことです。

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

この場合、両方の木の葉の走査順序は [5, 7, 8] で同一であるため、出力は True になります。

アルゴリズムの考え方

この問題は、再帰を使わずにスタック（LIFO構造）を利用して反復的に解くことができます。各木について、内部ノードの子をスタックに積みながら葉ノードを1つずつ取り出し、2つの木から取り出した葉の値を順番に比較していきます。途中で片方だけ葉が尽きたり、値が異なる場合は即座に False を返せばよいのです。

解決手順

• 新しいリスト s1 と s2 を用意する
• s1 に r1 を、s2 に r2 をそれぞれ挿入する
• s1 と s2 のどちらかが空になるまで、以下を繰り返す：
  • s1 または s2 の一方だけが空の場合は False を返す
  • r1_node := s1 の末尾ノードを取り出して削除する
  • r1_node が null でなく、かつ葉でない間、以下を繰り返す：
    • r1_node の右の子が null でなければ、s1 の末尾に追加する
    • r1_node の左の子が null でなければ、s1 の末尾に追加し、r1_node := s1 の末尾ノードを取り出して削除する
  • r2_node := s2 の末尾ノードを取り出して削除する
  • r2_node が null でなく、かつ葉でない間、以下を繰り返す：
    • r2_node の右の子が null でなければ、s2 の末尾に追加する
    • r2_node の左の子が null でなければ、s2 の末尾に追加する
    • r2_node := s2 の末尾ノードを取り出して削除する
  • r1_node が null で r2_node が null でない場合は False を返す
  • r1_node が null でなく r2_node が null の場合は False を返す
  • 両方とも null でない場合、値が異なれば False を返す
• ループを正常に抜けたら True を返す

Pythonでの実装例

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

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

    def is_leaf(self):
        return self.left == None and self.right == None

def solve(r1, r2):
    s1 = []
    s2 = []
    s1.append(r1)
    s2.append(r2)

    while len(s1) != 0 or len(s2) != 0:
        if len(s1) == 0 or len(s2) == 0:
            return False

        r1_node = s1.pop(-1)
        while r1_node != None and not r1_node.is_leaf():
            if r1_node.right != None:
                s1.append(r1_node.right)
            if r1_node.left != None:
                s1.append(r1_node.left)
            r1_node = s1.pop(-1)

        r2_node = s2.pop(-1)
        while r2_node != None and not r2_node.is_leaf():
            if r2_node.right != None:
                s2.append(r2_node.right)
            if r2_node.left != None:
                s2.append(r2_node.left)
            r2_node = s2.pop(-1)

        if r1_node == None and r2_node != None:
            return False
        if r1_node != None and r2_node == None:
            return False
        if r1_node != None and r2_node != None:
            if r1_node.val != r2_node.val:
                return False

    return True

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

root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)

print(solve(root1, root2))

入力

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

root2 = TreeNode(1)
root2.left = TreeNode(6)
root2.right = TreeNode(9)
root2.left.right = TreeNode(5)
root2.right.left = TreeNode(7)
root2.right.right = TreeNode(8)

出力

True

計算量の目安

• 時間計算量： O(n) — 各ノードは最大でも1回しかスタックに積まれないため、全ノード数 n に対して線形時間で処理できます。
• 空間計算量： O(h) — スタックには木の高さ h 程度のノードが保持されるため、メモリ使用量は木の高さに依存します。

まとめ

2つの二分木の葉の走査が一致するかどうかは、スタックを使った反復処理によって効率よく判定できます。再帰呼び出しを使わないため、深い木に対してもスタックオーバーフローの心配が少なく、実務的にも扱いやすいアプローチです。木構造の走査アルゴリズムの練習問題としても最適なので、ぜひ自分でも実装してみてください。