Python算法-深度优先搜索&广度优先搜索（DFS&BFS）

深度优先算法-DFS(Deep-first Search)

• 用到了递归的思想
• DFS: 从root节点开始，尽可能深的搜索一个分支，把一个分支搜索结束之后再进行下一个分支
• DFS主要应用：二叉树搜索+图搜索
• DFS和回溯算法的区别：回溯算法 = DFS + 剪枝

二叉树的遍历

144-前序遍历

• 前序遍历：根节点-左子树-右子树
• 递归+广度优先搜索

# 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 preorderTraversal(self, root: TreeNode) -> List[int]:
        def preorder(root:TreeNode):
            # 递归的终止条件:节点上没有值
            if root == None:
                return
            res.append(root.val)
            preorder(root.left)    
            preorder(root.right)   
        res = []
        preorder(root)
        return res 

• 栈+深度优先搜索

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        node = root
        if root == None:
            return res
        while stack or node:
            while node:
                res.append(node.val)
                stack.append(node)
                node = node.left
            node = stack.pop()        # 向上寻找根节点
            node = node.right         # 遍历右子树
        return res

94-中序遍历

• 中序遍历：左子树-根-右子树
• 递归+广度优先搜索

# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
        def inorder(root:TreeNode):
            if root == None:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        res = []
        inorder(root)
        return res

• 栈+深度优先搜索

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: 
            return []
        stack = [root]
        res = []
        while stack:  # 栈不为空就循环
            # 左子树中所有最左边的孩子进栈
            while root.left:
                stack.append(root.left)
                root = root.left
            cur = stack.pop()  # 弹出一个左孩子记为当前节点，看它有没有右孩子
            res.append(cur.val) # 每弹出一次记得记录一下
            if cur.right:  # 如果当前节点有右孩子的话，右孩子进栈，把这个右孩子当作新的根节点
                stack.append(cur.right)
                root = cur.right
        return res

145-后序遍历

• 后序遍历：左子树-右子树-根
• 递归+广度优先搜索

# 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 postorderTraversal(self, root: TreeNode) -> List[int]:
        def posterorder(root:TreeNode):
            if root == None:
                return 
            posterorder(root.left)
            posterorder(root.right)
            res.append(root.val)
        res = []
        posterorder(root)
        return res

• 栈+深度优先搜索

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        prev = None
        if root == None:
            return res
        while root or stack:
            # 遍历最左子树的的节点
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
 
            if not root.right or root.right == prev:
                res.append(root.val)
                prev = root
                root = None
            else:
                stack.append(root)
                root = root.right
        return res

102-层序遍历

• 队列+广度优先搜索

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        deque = []
        if root == None:
            return res
        deque.append(root)
        while deque:
            size = len(deque)         # size控制遍历的层数
            list = []
            while size > 0:
                cur = deque.pop(0)
                list.append(cur.val)
                if cur.left:
                    deque.append(cur.left)
                if cur.right:
                    deque.append(cur.right)
                size -= 1
            res.append(list)
        return res

• 方法2：深度优先搜索:一条路走到黑

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if root is None:
            return result
        
        self.dfs(root, result, 0)     # 从第零层开始
        return result

    def dfs(self, node, result, level):
        '''
        node: 当前的节点
        level：当前的层数
        '''
        # 递归终止条件
        if node is None:
            return
        if level > len(result)-1:      # 当前的层数大于result数组的长度-1时(0>-1)
            result.append([])          # 添加一个空数组，保证可以添加该层的元素
        result[level].append(node.val) # 添加元素到指定的层
        if node.left is not None:
            self.dfs(node.left, result, level+1)
        if node.right is not None:
            self.dfs(node.right, result, level+1)

617-合并二叉树

• 基本思想：使用 前序遍历
• 递归+深度优先搜索

# 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 mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        def dfs(r1, r2):
            if not r1:
                return r2
            if not r2:
                return r1
            r1.val = r1.val + r2.val               # 在r1上进行合并
            r1.left = dfs(r1.left, r2.left) 
            r1.right = dfs(r1.right, r2.right)
            return r1
        return dfs(root1, root2)

• 栈+广度优先搜索

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        if not root1:
            return root2
        if not root2:
            return root1
        stack = [(root1, root2)]
        while stack:
            r1, r2 = stack.pop(0)
            r1.val += r2.val
            # 如果r1和r2的左子树都不为空，就放到队列中
            # 如果r1的左子树为空，就把r2的左子树挂到r1的左子树上
            if r1.left and r2.left:
                stack.append((r1.left, r2.left))
            elif r1.left == None:
                r1.left = r2.left

            if r1.right and r2.right:
                stack.append((r1.right, r2.right))
            elif r1.right == None:
                r1.right = r2.right
        return root1

938-二叉搜索树的范围和
输入：root = [10, 5, 15, 3, 7, null, 18], low=7, high=15
输出：32
解释：返回值为位于[low, high]之间的所有结点的和

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        # 递归法
        result = 0
        if root is None:     # 递归的终止条件
            return 0
        leftSum = self.rangeSumBST(root.left, low, high)     # 左子树符合条件的和
        rightSum = self.rangeSumBST(root.right, low, high)   # 右子树符合条件的和
        result = leftSum + rightSum
        if root.val >= low and root.val <= high:        # 条件符合的值
            result += root.val
        return result

		10
	5		15
3	7		null	18

大树满足条件的和 等于 每个子树满足条件的数的和之和

2) DFS方法

class Solution:
    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        # dfs法
        result = 0
        queue = []               # 辅助队列
        queue.append(root)
        while len(queue) > 0:    # 队列不为空
            size = len(queue)
            while size > 0:
                cur = queue.pop()
                if cur.val >= low and cur.val <= high:
                    result += cur.val
                if cur.left is not None:               # 存在左子树
                    queue.append(cur.left)
                if cur.right is not None:              # 存在右子树
                    queue.append(cur.right)
                size -= 1                           # size控制每一层遍历
        return result

栈的长度
1						10
2				15	5
2		7	3
3	18	7	3

result = 0 + 10 + 15 + 18

200. 岛屿数量

输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
解释：
["1","1"] ； "1"
["1","1"] ； "1","1"

方法1：DFS

深度优先搜索必然会使用到递归

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if grid is None or len(grid) == 0:
            return 0
        result = 0
        row = len(grid)     # 行数
        col = len(grid[0])  # 列数
        # 找岛屿，同化
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1':
                    result += 1
                    self.dfs(grid, i, j, row, col)  # 同化：把 1 变为 0
        return result 
    
    def dfs(self, grid, x, y, row, col):
        # 递归的终止条件
        if x < 0 or y < 0 or x >= row or y >= col or grid[x][y] == '0': 
            return
        grid[x][y] = '0'   # 将 ‘1’变为 ‘0’
        # 上\下\左\右 查找可变为‘0’的区域
        self.dfs(grid, x-1, y, row, col)
        self.dfs(grid, x+1, y, row, col)
        self.dfs(grid, x, y-1, row, col)
        self.dfs(grid, x, y+1, row, col)

方法2：广度优先搜索

必须使用到辅助队列，用于判断

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if grid is None or len(grid) == 0:
            return 0
        result = 0
        row = len(grid)
        col = len(grid[0])
        q = []               # 辅助队列
        for i in range(0, row):
            for j in range(0, col):
                if grid[i][j] == '1':
                    result = result + 1
                    q.append([i,j])
                    grid[i][j] = '0'
                    while len(q) > 0:
                        cur = q.pop(0)   # 出队
                        x = cur[0]
                        y = cur[1]
                        # 如果位置坐标为‘1’同化之后添加坐标至队列中，
                        # 如果同化全部完成，坐标只会出列
                        if x-1 >= 0 and grid[x-1][y] == '1':
                            grid[x-1][y] = '0'
                            q.append([x-1, y])
                        if y-1 >= 0 and grid[x][y-1] == '1':
                            grid[x][y-1] = '0'
                            q.append([x, y-1])
                        if x+1 < row and grid[x+1][y] == '1':
                            grid[x+1][y] = '0'
                            q.append([x+1, y])
                        if y+1 < col and grid[x][y+1] == '1':
                            grid[x][y+1] = '0'
                            q.append([x, y+1])
        return result

方法3：并查集

找到共同的祖先

• Union(x,y)：合并x,y为同一个祖先
• Find(x)：找x的祖先 x=root[x]

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if grid == None or len(grid) == 0:
            return 0

        row = len(grid)
        col = len(grid[0])
        waters = 0               # 水域
        uf = UnionFind(grid)     # 实例化类
        for i in range(0, row):
            for j in range(0, col):
                if grid[i][j] == '0':
                    waters = waters + 1
                # 实现同化
                else:
                    directions = [[0,1], [0,-1], [1,0], [-1,0]]
                    for d in directions:
                        x = i + d[0]
                        y = j + d[1]
                        if x>=0 and x<row and y>=0 and y<col and grid[x][y]=='1':
                            uf.union(x*col+y, i*col+j)
        # 输出：（岛屿数+水域数） - 水域数
        return uf.getCount() - waters  


class UnionFind:
    def __init__(self, grid):
        # 由二维数组构建一个一维数组
        row = len(grid)
        col = len(grid[0])
        self.count = row * col
        self.root = [-1] * row * col   # 长度
        for i in range(0, row * col):
            self.root[i] = i     # 每一个树都有自己独立的祖先
    # 寻找祖先
    def find(self, x):
        if x == self.root[x]:
            return self.root[x]
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    # 只有找到最终的祖先后才union
    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            self.root[rootx] = rooty
            self.count -= 1
    # 返回合并之后的  岛屿数+水域数
    def getCount(self):
        return self.count  

733-图像渲染

对相同像素的相邻位置进行渲染

• 方法1：深度优先搜索

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        row = len(image)
        col = len(image[0])
        color = image[sr][sc]   # 获取需要渲染的像素
        # 当需要渲染的像素和目标像素值相等时，不需要渲染
        if color == newColor:
            return image
        # 深度优先搜索
        def dfs(r, c):
            if image[r][c] == color:
                image[r][c] = newColor
                # 向上渲染
                if r >= 1:
                    dfs(r-1, c)
                # 向下渲染
                if r+1 < row:
                    dfs(r+1, c)
                # 向左渲染
                if c >= 1:
                    dfs(r, c-1)
                # 向右渲染
                if c+1 < col:
                    dfs(r, c+1)
        dfs(sr, sc)
        return image

• 方法2：广度优先搜索

from queue import Queue
class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        if image[sr][sc] == newColor:
            return image
        # 设置四个方向的偏移量,上，下，左，右
        directions = {(-1,0), (1,0), (0,-1), (0,1)}
        # 构造一个队列，放入起始点
        que = Queue()
        que.put((sr, sc))
        # 记录初始颜色
        initcolor = image[sr][sc]
        # 当队列不为空
        while not que.empty():
            # 取出队列的点进行染色
            point = que.get()
            image[point[0]][point[1]] = newColor
            # 遍历四个方向
            for direction in directions:
                # 新的点（new_i, new_j）,行和列
                new_i = point[0] + direction[0]
                new_j = point[1] + direction[1]
                # 如果这个点在定义域内 且 颜色与初始点颜色相同
                if 0 <= new_i < len(image) and 0 <= new_j < len(image[0]) and image[new_i][new_j] == initcolor:
                    que.put((new_i, new_j))
        return image

695-岛屿的最大面积

给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

• 深度优先搜索

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        # i和j为网格的坐标位置
        for i, l in enumerate(grid):
            for j, n in enumerate(l):
                ans = max(self.dfs(grid, i, j), ans)
        return ans

    def dfs(self, grid, cur_i, cur_j) -> int:
        # 超出范围，递归终止条件-所有的网格节点全部变为0
        if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:
            return 0
        
        grid[cur_i][cur_j] = 0
        ans = 1

        # 对相邻位置进行搜索并记录每个岛屿的面积
        for di, dj in [[0,1], [0,-1], [1,0], [-1,0]]:
            next_i, next_j = cur_i + di, cur_j + dj
            ans += self.dfs(grid, next_i, next_j)
        return ans

• 栈+广度优先搜索

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        for i, l in enumerate(grid):
            for j, n in enumerate(l):
                cur = 0
                stack = [(i,j)]
                while stack:
                    cur_i, cur_j = stack.pop()
                    if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1:
                        continue
                    cur += 1
                    grid[cur_i][cur_j] = 0
                    for di, dj in [[0,1], [0,-1], [1, 0], [-1, 0]]:
                        next_i, next_j = cur_i + di, cur_j + dj
                        stack.append((next_i, next_j))
                ans = max(ans, cur)
        return ans