Pythonで二分木が対称木（シンメトリックツリー）かどうかを判定するプログラム

ある二分木が与えられたとき、その木が対称木（シンメトリックツリー）であるかどうかを判定します。対称木とは、鏡像（左右反転した像）をとったときに元の木と完全に一致するような木のことです。例えば、左右の子部分木が互いに鏡写しの関係になっている木は対称木とみなされます。

この判定を行うためのアプローチは以下の通りです。

解法の考え方

• 再帰的に処理を行う関数 solve(root, root) を呼び出します。同じノードを2つの引数として渡すのがポイントです。
• 比較対象の2つのノード（node1 と node2）がどちらも空（None）の場合、True を返します。
• どちらか一方だけが空の場合、構造が一致していないため False を返します。
• それ以外の場合は、「node1 の値と node2 の値が等しい」かつ「node1 の左部分木と node2 の右部分木が対称」かつ「node1 の右部分木と node2 の左部分木が対称」であるときに True を返します。

つまり、外側同士（左の左 ⇔ 右の右）と内側同士（左の右 ⇔ 右の左）をそれぞれ再帰的に比較していくことで、木全体が鏡像になっているかを確認できます。

実装例

以下にPythonでの実装例を示します。

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

class Solution(object):
    def isSymmetric(self, root):
        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))

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)

ob1 = Solution()
print(ob1.isSymmetric(root))

入力

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)

出力

True

この例では、根の値が1で、その左右に値2のノードが対称に配置され、さらにその下にも値3と4が鏡像の位置関係で並んでいるため、True（対称木である）が出力されます。

計算量について

このアルゴリズムは各ノードを一度ずつ訪問するため、時間計算量はノード数を n とすると O(n) です。また、再帰呼び出しの深さは木の高さに依存するため、空間計算量は最悪ケースで O(n)、バランスの取れた木では O(log n) となります。