Pythonで二分木を反転する方法：再帰を使った実装を解説

二分木の反転とは

二分木が与えられたとき、その左右の子ノードを入れ替えて「鏡像」のような木を作ることを二分木の反転（Invert Binary Tree）と呼びます。これはアルゴリズムの学習やコーディング面接でも頻出のトピックです。

例えば、次のような二分木があったとします。

これを反転すると、すべてのノードの左部分木と右部分木が入れ替わり、以下のような木になります。

解き方：再帰的アプローチ

この問題は再帰を使うと非常にシンプルに解けます。考え方は以下の3ステップです。

• ルートが None（null）であれば、そのまま返す（ベースケース）
• 現在のノードの左ポインタと右ポインタを入れ替える
• 左部分木と右部分木に対して再帰的に同じ処理を行う

この処理を全ノードに対して適用することで、木全体が反転されます。計算量はノード数を n とすると O(n)、空間計算量は再帰の深さに依存し、最悪の場合（偏った木）で O(n) となります。

Pythonでの実装例

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

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

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

def height(root):
    if root is None:
        return 0
    else:
        # 左右の部分木の高さをそれぞれ計算
        l_height = height(root.left)
        r_height = height(root.right)
        # 大きい方に1を足して返す
        if l_height > r_height:
            return l_height + 1
        else:
            return r_height + 1

def print_given_level(root, level):
    if root is None:
        return
    if level == 1:
        print(root.data, end=',')
    elif level > 1:
        print_given_level(root.left, level - 1)
        print_given_level(root.right, level - 1)

def level_order(root):
    h = height(root)
    for i in range(1, h + 1):
        print_given_level(root, i)

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)

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

    def solve(self, root):
        if not root:
            return
        # 左右の子を入れ替える
        temp = root.left
        root.left = root.right
        root.right = temp
        # 再帰的に処理を続ける
        self.solve(root.left)
        self.solve(root.right)

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

コードのポイント

• TreeNodeクラス：ノードの値と左右の子への参照を持つ基本的な二分木ノードです。
• make_tree / insert関数：リスト形式の入力から二分木を構築するための補助関数です。
• height / level_order関数：結果をレベル順（幅優先順）に出力して確認するためのものです。
• Solutionクラス：invertTree メソッドが本体で、solve メソッドにより各ノードの左右を再帰的に入れ替えます。

実行結果

入力

[1,2,2,3,4,None,3]

出力

1,2,2,3,None,4,3,

出力を見ると、元の木のレベル順走査結果と比較して、左右の子が正しく入れ替わっていることが確認できます。

まとめ

二分木の反転は、再帰の基本を理解するのに最適な問題です。「ベースケースを明確にする」「現在のノードでの処理を定義する」「子ノードに処理を委ねる」という再帰の型を押さえれば、短いコードで美しく解くことができます。ぜひ自分でも手を動かして実装してみてください。