1. 回顾数据结构&算法

让我们重新回顾一下数据结构的整体分类和算法，并自己内心说明各个数据结构的特性，回忆算法的思想和代码模板。

1.1 一维数据结构

基础的有：数组（查询快，插入操作较慢，需要重新分配空间）、链表（查询慢，插入比数组快）
高级的有：栈stack（先进后出）、队列queue（先进先出）、双端队列deque（适用于FIFO和LIFO两个场景）、集合Set（无重复元素集合）、映射map(hash 或者 map)、etc

1.2 二维数据结构

基础的有：树tree、图Graph（链表是特殊化的树，树是特殊化的图）
高级的有：二叉搜索树binary search tree (red-black tree,AVL)、堆heap、并查集disjoint Set、字典树 Trie、etc

1.3 特殊

位运算 bitwise、布隆过滤器 BloomFilter
LRU Cache
注意：在脑海中回忆数据结构的特点

1.4 算法

if-else，switch ——> branch
for,while loop ——> Iteration
递归 Recursion(Divide & Conquer,backtrace)
搜索Search：深度优先搜索 Depth first Search, 广度优先搜索Breadth first search , A*，etc
动态规划 Dynamic Programming
二分查找 binary Search
贪心算法 Greedy
数学 Math，几何 Geometry

注意：在脑海中回忆上面的各种算法思想和代码模板

默写上一章节中：树的定义和遍历模板，分治和回溯的代码模板
注意：递归、分治、回溯三个算法的异同点。
回顾完成后我们开始学习深度优先搜索和广度优先搜索这两个算法

2.深度优先搜索算法

首先遍历搜索指在图（状态集）或树中寻找特定节点，回忆树的定义和遍历代码模板
特点：

每个节点都要访问一次
每个节点只访问一次
对节点的访问顺序不同分为dfs和bfs

2.1 遍历顺序

2.2 dfs代码模板**

dfs-递归版本

visited = set()
def dfs(node, visited):
    if node in visited: # terminator
        # already visited
        return
    visited.add(node)
    # process current node here.
    ...
    for next_node in node.children():
        if not next_node in visited:
            dfs(next node, visited)

dfs-非递归写法

def DFS(self, tree):
    if tree.root is None:
        return []
    visited, stack = [], [tree.root]
    while stack:
        node = stack.pop()
        visited.add(node)
        process (node)
        nodes = generate_related_nodes(node)
        stack.push(nodes)
    # other processing work
    ...

3. 广度优先搜索算法

3.1 遍历顺序

3.2 广度优先搜索算法-bfs代码模板

bfs非递归代码模板：

def BFS(graph, start, end):
    queue = []
    queue.append([start])
    visited.add(start)
    while queue:
        node = queue.pop()
        visited.add(node)
        process(node)
        nodes = generate_related_nodes(node)
        queue.push(nodes)

bfs递归代码模板：

visited = set()
def dfs(node, visited):
    visited.add(node)
    # process current node here.
    ...
    for next_node in node.children():
        if not next_node in visited:
            dfs(next node, visited)

4. 练习

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/#/description
2. https://leetcode-cn.com/problems/minimum-genetic-mutation/#/description
3. https://leetcode-cn.com/problems/generate-parentheses/#/description
4. https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/#/description

HomeWork
1. https://leetcode-cn.com/problems/word-ladder/description/
2.https://leetcode-cn.com/problems/word-ladder-ii/description/
3.https://leetcode-cn.com/problems/number-of-islands/
4.https://leetcode-cn.com/problems/minesweeper/description/

数据结构与算法

8. 深度优先搜索&广度优先搜索