dfs，bfs

https://www.jianshu.com/p/a753d5c733ec

dfs

1 递归实现

def dfs(当前节点,子节点)
    for node in 子节点
        dfs(node,new 子节点)

310. 最小高度树

#### root 当前节点 path子节点 depth 深度
dfs(root,path,depth)

695. 岛屿的最大面积

###grid全部格点 cur_i，cur_j 当前节点的位置，用+1-1可以确定子节点
dfs(self, grid, cur_i, cur_j) :

2 迭代实现

bfs

1 迭代实现

root进队，root出队，root的子节点【a,b,c】进队，a出队，a的子节点进队，b出队，b的子节点进队。。。

访问顺序（出队顺序）：root a b c 。。。

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if root==None:
            return []
        ans = []
        q = [root]
        while q:
            # length = len(q)
            # arr = []
            # for _ in range(length):
            node = q.pop(0)
            # arr.append(node.val)
            for chd in node.children:
                q.append(chd)
            # if arr:
            ans.append(node.val)
        return ans

429. N 叉树的层序遍历

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        ans = []  ##结果
        q = [root] ##队列
        while q:
            length = len(q)
            arr = [] #出队
            for _ in range(length):
                node = q.pop(0)
                if not node: 
                    continue
                arr.append(node.val)
                for chd in node.children:
                    q.append(chd)
            if arr:
                ans.append(arr)
        return ans

2 递归实现

应用选择

时间复杂度都为O（n）,n为全部节点

1. BFS是用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解，因为BFS搜索过程中遇到的解一定是离根最近的，所以遇到一个解，一定就是最优解，此时搜索算法可以终止。这个时候不适宜使用dfs，因为DFS搜索到的解不一定是离根最近的，只有全局搜索完毕，才能从所有解中找出离根的最近的解。（当然这个DFS的不足，可以使用迭代加深搜索ID-DFS去弥补）
2. DFS适合搜索全部的解，而正因为要搜索全部的解，那么BFS搜索过程中，遇到离根最近的解，并没有什么用，也必须遍历完整棵搜索树；DFS搜索会搜索全部，但是相比之下 DFS不用记录过多信息，所以搜素全部解的问题，DFS显然更加合适。空间优劣上，DFS是有优势的，DFS不需要保存搜索过程中的状态，而BFS在搜索过程中需要保存搜索过的状态，而且一般情况需要一个队列来记录。

和回溯的关系

回溯是算法思想，dfs和bfs是搜索解空间的手段

参考

https://www.jianshu.com/p/e81a16a6f771

https://blog.csdn.net/weixin_41894030/article/details/95317440