同模BFS+DFS in Tree and Graph 2020
2020-03-29 本文已影响0人
9_SooHyun
BFS
BFS基于队列，层层遍历每个节点只访问了一次，时间复杂度O(N)
- 关于Tree的BFS：
首先root节点入队，然后将当前批次队列中的节点出队，并将它们的孩子入队
关于二叉树的层次遍历模板如下
# 使用【队列】进行层次遍历
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
res = list()
# 如果树根存在，那么才开始层次遍历
if root:
queue = list()
queue.append(root)
# 核心代码开始
while queue:
l = len(queue)
for i in range(l):
# 注意，这里是不断pop首个元素
out = queue.pop(0)
# 出队列，将val加入结果集
res.append(out.val)
# 将出队元素的合法孩子们入队
# 如果有左孩子
if out.left:
queue.append(out.left)
# 如果有右孩子
if out.right:
queue.append(out.right)
return res
notes：因为实现层次遍历是利用了队列不断弹出队首元素，这里使用list.pop(0)来实现，时间复杂度较高，弹出一次后面所有元素都得前移一位
- 关于图的BFS：
与Tree的BFS大同小异，主要2个小区别：
1、tree只有1个root作为BFS的源点，而图可以有多个源点，所以首先需要把多个源点都入队；或者认为图存在一个虚root，这些源点都是虚root的孩子
2、tree结构不存在回路，不需要标志某个节点是否访问过，但图必须标志节点是否已经被访问过。【可以额外使用字典/列表登记，但更巧的是直接原地修改元素值进行标记】
例题1
一个 N x N 的grid，每个元素要么是1要么是0，1表示陆地，0表示海洋，返回距离陆地最远的海洋到离它最近的陆地区域的距离。这里的所有距离指曼哈顿距离。如果全是1或者0，返回-1
思路：这是一个图的BFS，所有的1可以组成源点集，每次向外扩散，最后被扩散到的海洋就是最远的海洋。扩散过程中维护一个变量step表示曼哈顿距离
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
position = list()
# 先求出所有的陆地位置，加入队列position
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
position.append((i, j))
# 全部是陆地或者海洋
if not position or len(position) == m*n:
return -1
## 下面开始层次遍历 ##
# 多块陆地按上下左右四个方向向海洋深处扩散，最后被扩散到的那片海洋就是目标海洋，扩散需要的步长就是曼哈顿距离
# 字典visited_d用于登记节点是否被访问过
visited_d = dict()
step = 0
while position:
step += 1
l = len(position)
for i in range(l):
# 节点出队
p = position.pop(0)
# 孩子入队
x, y = p[0], p[1]
for child in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
# 如果孩子没有被扩散到
if 0 <= child[0] < m and 0 <= child[1] < n and child not in visited_d:
# 登记
visited_d[child] = 1
# 入队
position.append(child)
return step-1
优化：上面的方法中，使用字典visited_d登记节点是否被访问过，额外开辟了空间，可以原地修改grid表示当前位置与1的距离
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
position = list()
# 先求出所有的陆地位置，加入队列position
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
position.append((i, j))
# 全部是陆地或者海洋
if not position or len(position) == m*n:
return -1
## 下面开始层次遍历 ##
# 多块陆地按上下左右四个方向向海洋深处扩散，最后被扩散到的那片海洋就是目标海洋，扩散需要的步长就是曼哈顿距离
# 使用字典visited_d登记节点是否被访问过 -> 原地修改grid进行登记
# visited_d = dict()
step = 0
while position:
step += 1
l = len(position)
for i in range(l):
# 节点出队
p = position.pop(0)
# 孩子入队
x, y = p[0], p[1]
for child in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
# 如果孩子没有被扩散到
if 0 <= child[0] < m and 0 <= child[1] < n and grid[child[0]][child[1]] == 0:
# 原地修改grid实现登记
grid[child[0]][child[1]] = step
# 入队
position.append(child)
return step-1
DFS
DFS基于栈，也是每个节点只访问了一次，时间复杂度O(N)
巧的是，我们只需在层次遍历的基础上改动【一处】，即改变pop元素的位置，就实现了BFS到DFS的转变
栈总是弹出最后一个元素，而队列总是弹出队首元素，因此将pop(0)改为pop()即可
# 使用【栈】进行深度优先遍历
class Solution:
def DFS(self, root: TreeNode) -> List[int]:
res = list()
# 如果树根存在，那么才开始深度优先遍历
if root:
stack = list()
stack.append(root)
# 核心代码开始
while stack:
# 注意，这里是不断pop最尾元素来模拟栈
out = stack.pop()
# 出队列，将val加入结果集
res.append(out.val)
# 将出队元素的合法孩子们入队。注意，如果按左孩子-右孩子顺序入栈，由于后进先出原则，右孩子所在的子树会优先访问
# 要实现前序遍历的话，按右孩子-左孩子的顺序入栈即可
# 如果有左孩子
if out.left:
stack.append(out.left)
# 如果有右孩子
if out.right:
stack.append(out.right)
return res
例
leetcode200岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围
思路：res为函数返回值，初始化为0。遍历整个grid，如果发现是1，说明此处有岛屿，res自增1，然后进行dfs，每访问一个为'1'的结点，将其置为2以标记该位置已访问
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
m = len(grid)
n = len(grid[0])
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
res += 1
# dfs
self.dfs(grid, i, j, m, n)
return res
def dfs(self, grid, i, j, m, n):
stack = list()
stack.append((i, j))
while stack:
l = len(stack)
for _ in range(l):
p = stack.pop()
# 标记该位置已访问
grid[p[0]][p[1]] = 2
# 孩子
for a,b in [1,0],[0,1],[-1,0],[0,-1]:
P = p[0]+a
Q = p[1]+b
if 0 <= P < m and 0 <= Q < n:
if grid[P][Q] == '1':
stack.append((P, Q))
注意：
与BFS同源的DFS只适合于做前序遍历，而不能模拟中序遍历和后序遍历
非递归的bfs和dfs解决同一问题：翻转二叉树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
# # bfs翻转-一层一层翻
# if not root:
# return root
# ori_root = root
# queue = []
# queue.append(root)
# while queue:
# l = len(queue)
# for i in range(l):
# p = queue.pop(0)
# if p is not None:
# # 交换
# temp = p.left
# p.left = p.right
# p.right = temp
# queue.append(p.left)
# queue.append(p.right)
# return ori_root
# dfs翻转
if not root:
return root
ori_root = root
queue = []
queue.append(root)
while queue:
p = queue.pop()
if p is not None:
# 交换
temp = p.left
p.left = p.right
p.right = temp
queue.append(p.left)
queue.append(p.right)
return ori_root
