深さ優先探索と幅優先探索

# 1. 要約

- 木構造の探索として、深さ優先探索（Depth First Search）と、幅優先探索（Breadth First Search）がある
- 深さ優先探索は、探索できるところまで深く潜る戦略で、再帰またはスタックを使って実装される
- 幅優先探索は、各階層を広く横断的に探索する戦略で、キューを使って実装される

# 2. 幅優先探索
## 2.1. 幅優先探索とは？

幅優先探索は、各階層のノードを順番に探索していく。最短経路を求める問題などに使われる。

![download.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3618276/b5f7136b-f8e0-4e8b-a419-b06f44409602.png)

画像は[hackerearth](https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/)より

## 2.2. 幅優先探索の実装
幅優先探索の実装を行う。問題はLeetCodeの[112. Path Sum](https://leetcode.com/problems/path-sum/description/?envType=problem-list-v2&envId=breadth-first-search)を使う。

問題文
> Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.

二分木の根と、整数のtargetSumが与えられるので、もしその木に根から葉へのパスがあり、そのパス上の全ての値を合計するとtargetSumと等しくなる場合はTrueを返す。葉とは、子を持たないノードです。

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        # 根がNoneである（=二分木が存在しない）場合は、Falseを返す
        if root is None:
            return False

        # queueを利用して、幅優先択を行う
        # (現在探索しているノード, ノード探索時点での合計値)を保持している
        queue = deque([(root, root.val)])
        
        while queue:
            node, sum = queue.popleft()

            # node.left, node.rightがともにNoneの場合、nodeは「葉」となる
            # nodeが葉の時点での合計値 sum が targetSum と等しい場合、Trueになる
            if node.left is None and node.right is None and sum == targetSum:
                return True

            # node.leftがNoneでない場合、node.leftをqueueに追加する
            # このとき、sum の更新も行う
            if node.left:
                queue.append((node.left, sum + node.left.val))

            # node.leftと同様のことを node.right でも行う
            if node.right:
                queue.append((node.right, sum + node.right.val))

        # 全て探索して while を抜けた場合、根から葉までの合計値で targetSum となるものが見つからなかったので Falseを返す。
        return False
```

# 3. 深さ優先探索
## 3.1. 深さ優先探索とは？
深さ優先探索とは、探索できるところまで深く探索していき、行き止まりになったら戻るという方法。全ての経路を調べたいときや、再帰的な問題に向いている。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3618276/7bef238e-5e5b-41f3-8e52-1b6c3b45de5d.png)

画像は [Wikipedia: Depth-First Searchより](https://en.wikipedia.org/wiki/Depth-first_search)

深さ優先探索は、木構造においては「どのタイミングでノードの値を処理するか」によって、次の3つに分類することができる。

| 名前 | 処理順序 | 説明 |
|-----|----------|-----|
|前順(pre-order) | 根->左->右|ノードに訪れた直後に処理する|
|間順(in-order)|左->根->右| 左の探索が終わった時点で処理|
|後順（post-order)|左->右->根|左右の子をすべて処理した後にノードを処理する| 

## 3.2. 前順操作の実装
以下の木構造を考える。

```mermaid
graph TD
    A1["1"]
    A2["2"]
    A9["9"]
    A3["3"]
    A6["6"]
    A10["10"]
    A13["13"]
    A4["4"]
    A5["5"]
    A7["7"]
    A8["8"]
    A11["11"]
    A12["12"]
    A14["14"]
    A15["15"]

    A1 --- A2
    A1 --- A9
    A2 --- A3
    A2 --- A6
    A9 --- A10
    A9 --- A13
    A3 --- A4
    A3 --- A5
    A6 --- A7
    A6 --- A8
    A10 --- A11
    A10 --- A12
    A13 --- A14
    A13 --- A15
```

これに前順操作を用いて探索していき、探索した順に表示すると、1から15まで昇順になるはずである。Pythonコードは以下の通りである。

```python
# ---------- ここから、BinaryTreeまで全ての探索で共通である ----------
from collections import deque

class Node:
    def __init__(self, value=0):
        self.value = value
        self.left = None
        self.right = None
        
class BinaryTree:
    def __init__(self, array):
        self.root = Node(array[0]) if array else None
        queue = deque([self.root])
        i = 1
        
        while i < len(array):
            current = queue.popleft()
            
            if i < len(array):
                current.left = Node(array[i])
                queue.append(current.left)
                i += 1
                
            if i < len(array):
                current.right = Node(array[i])
                queue.append(current.right)
                i += 1
                
# ---------- ここまでのコードは、全ての探索で共通である。 ----------

def pre_order(arr):
    binary_tree = BinaryTree(arr)
    stack = [binary_tree.root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.value)
        
        if node.right:
            stack.append(node.right)
            
        if node.left:
            stack.append(node.left)
    
    return result

pre  = [1, 2, 9, 3, 6, 10, 13, 4, 5, 7, 8, 11, 12, 14, 15]  # 前順（pre-order）
print(pre_order(pre)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
```

`BinaryTree`オブジェクトでは、リストを二分探索木に変換している。前順の探索は、`pre_order`関数で実装している。

この関数では、まず最初に `BinaryTree`オブジェクトを初期化し、ルートノードを作成する。そして stack を使って探索を行っていく。スタックの性質（=Last-In First-Out)より、左右の子ノードがある場合は、右側を先にスタックへ入れて、左側を後にいれる

こうすることで、取り出すときには左のノードが最初に処理される。

## 3.3. 間順操作の実装
以下の木構造を考える。

```mermaid
graph TD
    A1["1"]
    A2["2"]
    A9["9"]
    A3["3"]
    A6["6"]
    A10["10"]
    A13["13"]
    A4["4"]
    A5["5"]
    A7["7"]
    A8["8"]
    A11["11"]
    A12["12"]
    A14["14"]
    A15["15"]

    A8 --- A4
    A8 --- A12
    A4 --- A2
    A4 --- A6
    A12 --- A10
    A12 --- A14
    A2 --- A1
    A2 --- A3
    A6 --- A5
    A6 --- A7
    A10 --- A9
    A10 --- A11
    A14 --- A13
    A14 --- A15
```

これに間順操作を用いて探索していき、探索した順に表示すると、1から15まで昇順になるはずである。Pythonコードは以下の通りである。なお、前順操作と重複する部分のコードについては省略する。

```python
def in_order(arr):
    binary_tree = BinaryTree(arr)
    stack = []
    current = binary_tree.root
    result = []
    
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
            
        current = stack.pop()
        result.append(current.value)
        current = current.right
        
    return result

in_  = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15]  # 間順（in-order）
print(in_order(in_)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
```

前順操作と比べると少し複雑なコードである。特徴としては、while ループの入れ子である。

1. current に左の子がある限り、ひたすら下っていく
2. 左端（葉ノード）まで行ったら、その時点でstackからノードを取り出して値を記録
3. そのノードの右の子に移動して、同じ流れを繰り返す

ノードの右側が None の時は、内側の while ループはスキップされ、次のスタック操作に移る。これにより、探索は自動的に正しい順序で進むようになっている。


## 3.4. 後順操作の実装
以下の木構造を考える。

```mermaid
graph TD
    A1["1"]
    A2["2"]
    A9["9"]
    A3["3"]
    A6["6"]
    A10["10"]
    A13["13"]
    A4["4"]
    A5["5"]
    A7["7"]
    A8["8"]
    A11["11"]
    A12["12"]
    A14["14"]
    A15["15"]

    A15 --- A7
    A15 --- A14
    A7 --- A3
    A7 --- A6
    A14 --- A10
    A14 --- A13
    A3 --- A1
    A3 --- A2
    A6 --- A4
    A6 --- A5
    A10 --- A8
    A10 --- A9
    A13 --- A11
    A13 --- A12
```

これに後順操作を用いて探索していき、探索した順に表示すると、1から15まで昇順になるはずである。Pythonコードは以下の通りである。

```python
def post_order(arr):
    binary_tree = BinaryTree(arr)
    
    stack = [binary_tree.root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.value)
        
        if node.left:
            stack.append(node.left)
            
        if node.right:
            stack.append(node.right)
            
    return result[::-1]

post = [15, 7, 14, 3, 6, 10, 13, 1, 2, 4, 5, 8, 9, 11, 12]  # 後順（post-order）
print(post_order(post)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
```

後順操作は、左->右->根であった。実装では根->右->左の順に探索していき、最後に反転をさせている。

# 4. 終わりに
ここまで読んでくれてありがとうございました。もし間違いがあれば、コメントで教えてください。