Leetcode 100. Same Tree

Problem

この問題は、二分木の構造と値の両方が同一であるかどうかを判断するというものです。

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

この場合は同一。

この場合は非同一です。

Approach #1 Depth-First Search (DFS) using Recursion

深さ優先探索（DFS: Depth-First Search）を使って解くことができます。

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # 両方のノードがNoneの場合
        if not p and not q:
            return True
        # 一つだけNoneである場合
        if not p or not q:
            return False
        # 二つのノードの値が異なる場合
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Approach #2 Depth-First Search (DFS) using Stack

再帰を使わない形でのDFSを使って解くこともできます。一般的に、再帰を使わないDFSはスタックを利用して解くことができます。

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:

        stack = [(p, q)]

        while stack:
            node_p, node_q = stack.pop()
            if not node_p and not node_q:
                continue
            elif not node_p or not node_q:
                return False

            if node_p.val != node_q.val:
                return False
            else:
                stack.append((node_p.left, node_q.left))
                stack.append((node_p.right, node_q.right))
        return True

Approach Breadth-First Search (BFS)

再帰を使わず、幅優先探索 (BFS: Breadth-First Search) を使用することもできます。Pythonのキューを使って、二つの木を同時に探索します。

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:

        queue = collections.deque([(p, q)])

        while queue:
            node_p, node_q = queue.popleft()
            if not node_p and not node_q:
                continue
            elif not node_p or not node_q:
                return False

            if node_p.val != node_q.val:
                return False
            else:
                queue.append((node_p.left, node_q.left))
                queue.append((node_p.right, node_q.right))
        return True

ここで、queueに入れる時に collections.deque([(p, q)]) のようにリストとして保存することに気をつけてください。deque((p, q)) の形式では期待通りに動作しません。これは、deque が受け取る引数がシーケンス（例えば、リストやタプル）であることが期待されているからです。

具体的には、deque((p, q)) を実行すると、dequeは二つのノード p と q を別々のエントリとして保存します。一方、deque([(p, q)]) を実行すると、二つのノード p と q がペア（タプル）として一つのエントリに保存されます。

Complexity

Approach #1, #2 : Depth-First Search (DFS)

• Time complexity : O(n)。ここで、nはツリーのノードの数です。最悪の場合、全てのノードを一度ずつ訪れる必要があります。
• Space complexity : O(d)。ここで、dはツリーの深さです。再帰を用いる場合でも用いない場合でも、ツリーの深さに比例します。平衡二分木の場合、ツリーの深さDはlog(N)になるのでSpace complexityもツリーの深さDはO(log(N))になります。一方、一方向に伸びるツリーの場合、ツリーの深さDはNとなるので、O(n)となります。

Approach #3 : Breadth-First Search (BFS)

• Time complexity : O(n)。ここで、nはツリーのノードの数です。最悪の場合、全てのノードを一度ずつ訪れる必要があります。
• Space complexity : O(w)。ここで、dはツリーの最大の幅（あるレベルに存在する最大ノード数）です。幅優先探索では、キューに保存されるノードは同一レベルのものとなり、その数はツリーの幅に比例します。一方向に伸びるツリーの場合、各レベルでのノード数(幅) は1となるため、O(1)となります。一方、完全な二分木の場合、ツリーの最下層には約N/2のノードが存在するため、Space complexityはO(N)となります。

Reference