Leetcode 226. Invert Binary Tree

Problem

Binary treeを左右反転させるという問題です。

Given the root of a binary tree, invert the tree, and return its root.

InputとOutputの例は次になります。

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Key Idea

再帰を使う方法と使わない方法の２通りを考えます。

Approach #1 Recursive (Depth First Search)

再帰を使う方法では、深さ優先探索（DFS）が用いられます。深さ優先探索は、まず一つの経路を最深部まで探索し、それが終わったら次の経路を探索する方法です。

class Solution:
    def invertTree(self, root):
        if root is None:
            return None

        
        tmp = root.left
        root.left = root.right
        root.right = tmp
        # root.left, root.right = root.right, root.left でも可

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

Approach #2 Iterative (Breadth-First Search)

幅優先探索（BFS）の考え方で、Queueを使って解くこともできます。

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        queue = collections.deque([root])
        while queue:
            current = queue.popleft()

            tmp = current.left
            current.left = current.right
            current.right = tmp
            # current.left, current.right = current.right, current.left でも可

            if current.left:
                queue.append(current.left)
            
            if current.right:
                queue.append(current.right)
        
        return root

Complexity

Time complexityはO(n)です（nはノードの数）。どちらの解法とも、各ノードを一度ずつ訪れるからです。

Space complexity については、少し違いがあります。
再帰の場合は、再帰呼び出しによるスタックの深さに依存します。最悪の場合（つまり、すべてのノードが1本の線上に並んだような場合）、スタックの深さはO(n)となります。しかし、完全二分木の場合、スタックの深さはO(log n)となります。

一方、キューを使用する場合は、キューに格納されるノードの最大数に依存します。幅優先探索（BFS）では、一度に最大で全てのリーフノードがキューに格納される可能性があります。したがって、最悪の場合（つまり、最も広いレベルがリーフノードで占められている場合）、空間複雑度はO(n)となります。

したがって、平均的な場合には再帰の方が空間効率がよい可能性がありますが、最悪の場合にはスタックオーバーフローを考慮するとキューを使用した方が安全であると言えます

Reference