LeetCode 226 「Invert Binary Tree」の 解説

問題概要

Invert Binary Treeは、二分木の左右の子を反転させる問題です。具体的には、以下の図のように、二分木の各ノードの左右の子を入れ替えることによって、左右が反転された二分木を作成することが目的です。

解法

二分木の左右の子を反転させる方法には2通り考えられます。
・再帰を使用する方法
・スタックを使用する方法

今回は再帰を使用する方法の解説をします

まず、二分木のルートノードを入力として受け取ります。そのルートノードの左右の子を入れ替え、その左右の子それぞれについて同様の操作を再帰的に行います。このとき、再帰呼び出しの戻り値をそのまま返すようにします。

実装例

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        
        root.left = right
        root.right = left
        
        return root

計算量

時間計算量 O(n)
空間計算量 O(n)
二分木の各ノードを一度だけ訪問するため、時間計算量はO(n)です。
また、再帰の深さがnである場合、スタックの使用によってO(n)の追加空間が必要なため、空間計算量はO(n)です。

結果

Invert Binary Treeは、二分木の左右の子を反転させることで、左右が反転された二分木を作成する問題です。再帰を使用することで、比較的簡単に解くことができます。再帰の深さがnである場合、スタックの使用によってO(n)の追加空間が必要になりますが、時間計算量はO(n)となるため、十分に効率的な解法です。