Pythonで二分木を反転するプログラムの実装方法

二分木の根ノードが与えられたとき、それを「反転」することを考えます。反転とは、左部分木と右部分木を入れ替え、さらにその子ノードについても同様の入れ替えを再帰的に行う操作です。

問題の例

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

この木を反転すると、出力は次のようになります。

解き方のアプローチ

この問題は、再帰を用いることでシンプルに解くことができます。手順は以下の通りです。

• ノードを受け取る solve() メソッドを定義します。

• 根ノードが null（None）の場合は、何もせずに return します。

• 根の左の子に solve(右の子) の結果を代入します。

• 根の右の子に solve(左の子) の結果を代入します。

• 根ノードを返します。

ポイントは、左右を同時にスワップするため、Pythonのタプル代入（a, b = b, a）を活用すると簡潔に書けることです。一時変数を用意しなくても、両側の値を同時に評価して入れ替えられます。

実装例

以下のコードで実際の動作を確認してみましょう。

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

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=', ')
        inorder(root.right)

class Solution:
    def solve(self, root):
        if not root:
            return
        root.left, root.right = self.solve(root.right), self.solve(root.left)
        return root

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
inv = ob.solve(root)
inorder(inv)

入力

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)

出力

15, 10, 7, 5, 4,

コードの解説

まず TreeNode クラスで各ノードの値（val）、左子（left）、右子（right）を保持する構造を定義しています。inorder 関数は中順走査（in-order traversal）を行い、結果を確認するための補助関数です。

Solution クラスの solve メソッドでは、再帰の終了条件として if not root: return を設け、ノードが存在しない場合に処理を終えます。その後、root.left, root.right = self.solve(root.right), self.solve(root.left) の1行で、左右の部分木をそれぞれ再帰的に反転しながら同時にスワップしています。

このアルゴリズムの計算量は、すべてのノードを一度ずつ訪問するため O(n) です。また、再帰の深さは木の高さに依存するため、バランスの取れた木では O(log n)、最悪ケース（線形に偏った木）では O(n) のスタック領域が必要になります。