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.

この場合は同一。
![image](https://assets.leetcode.com/uploads/2020/12/20/ex1.jpg)


この場合は非同一です。
![image](https://assets.leetcode.com/uploads/2020/12/20/ex2.jpg)

https://leetcode.com/problems/same-tree/description/


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

```Python
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はスタックを利用して解くことができます。

```python
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のキューを使って、二つの木を同時に探索します。


```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
https://www.youtube.com/watch?v=vRbbcKXCxOw