Pythonで二分木が対称（シンメトリック）かどうかを判定する方法

本記事では、Pythonを使って二分木が対称（シンメトリック）であるかどうかを判定するアルゴリズムを解説します。

対称な二分木とは？

ある二分木について、鏡像（左右反転した像）をとったときに元の木と完全に一致する場合、その木は「対称な木」であると定義されます。例えば、次のような2つの木を考えてみましょう。

• 1つ目の木：左部分木と右部分木が鏡像の関係になっている → 対称
• 2つ目の木：一部のノード配置が左右で異なる → 非対称

解法のアプローチ

この問題は、再帰（recursion）を使うことでエレガントに解くことができます。基本的な考え方は、「根の左側と右側を同時にたどり、互いに鏡像の関係にあるかを確認する」というものです。具体的には以下の手順で判定を行います。

• solve(root, root) のように、同じ根を2つの引数として関数を再帰的に呼び出します。
• node1 と node2 がどちらも空（None）の場合は true を返します（比較対象がないため対称とみなせる）。
• node1 または node2 の片方だけが空の場合は false を返します（構造が不一致のため）。
• 上記以外の場合は、「node1.data == node2.data かつ solve(node1.left, node2.right) かつ solve(node1.right, node2.left)」が成立するときに true を返します。ポイントは、左の子と相手の右の子、右の子と相手の左の子をそれぞれ比較する点です。

実装例

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

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

def insert(temp,data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.solve(root,root)

    def solve(self,node1,node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2:
            return False
        return node1.data == node2.data and \
               self.solve(node1.left,node2.right) and \
               self.solve(node1.right,node2.left)

tree1 = make_tree([1,2,2,3,4,4,3])
tree2 = make_tree([1,2,2,3,4,None,3])
ob1 = Solution()
print(ob1.isSymmetric(tree1))
print(ob1.isSymmetric(tree2))

入力

tree1 = make_tree([1,2,2,3,4,4,3])
tree2 = make_tree([1,2,2,3,4,None,3])

出力

True
False

コードの解説

このプログラムでは、まず TreeNode クラスで二分木のノードを表現し、insert 関数と make_tree 関数を使ってリストから二分木を構築しています。

Solution クラスの isSymmetric メソッドが本体であり、内部で solve メソッドを再帰的に呼び出しています。solve メソッドでは以下のロジックで対称性を判定します。

1. 両方のノードが None：そこまでの経路は対称なので True を返す。
2. 片方だけ None：構造が崩れているため False を返す。
3. 両方存在する場合：値が等しく、かつ「node1の左 vs node2の右」「node1の右 vs node2の左」がすべて対称であれば True を返す。

実行結果として、完全に対称な tree1 に対しては True、途中に None を含み非対称な tree2 に対しては False が出力され、正しく判定できていることがわかります。

計算量

このアルゴリズムは各ノードを一度ずつ訪問するため、時間計算量は O(n)（n はノード数）、再帰呼び出しによる空間計算量も最悪ケースで O(n) となります。