【算法模板】DFS秒杀模板—附练习题（阳光号启航）（二）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        //判断一个根节点是是否为空，如果为空则返回0。
        if(root == null){
            return 0;
        }
        //进行一个递归判断左子树和右子树的最大值并加上一。
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#思路是和Java版本的一样的。
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1

class Solution {
    //设置返回结果集
    int res = 0;
    public int numIslands(char[][] grid) {
        //获取grid的长和宽。
        int m = grid.length;
        int n = grid[0].length;
        //for循环遍历整个grid表格。
        for (int i = 0 ; i < m ; i++ ){
            for (int j = 0 ; j < n ;j ++ ){
                //发现陆地‘1’的时候res加一，且是用dfs沉岛。
                if (grid[i][j] == '1'){
                    res += 1;
                    dfs(i,j,m,n,grid);
                }
            }
        }
        //返回最后结果
        return res;
    }
    //定义dfs方法，用来沉岛
    void dfs(int x , int y,int m , int n , char[][] grid) {
        //判断如果越界和不是陆地则结束递归。
        if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y]== '0') return ;
        //如果grid[x][y] == '1'，则把它变为'0'且继续使用DFS遍历x,y四周的岛屿。
        grid[x][y] = '0';
        dfs(x - 1,y,m,n,grid);
        dfs(x + 1,y,m,n,grid);
        dfs(x , y + 1,m,n,grid);
        dfs(x , y - 1,m,n,grid);
    }
}

class Solution:
    #Python的大体思路是和上面Java的一样，这里我就不再过多的叙述了。
    def numIslands(self, grid: List[List[str]]) -> int:
        x = len(grid)
        y = len(grid[0])
        def dfs (grid,i,j):
            if i < 0 or j < 0 or i >=  x or j >= y or grid[i][j] =='0':
                return 
            grid[i][j] = '0'
            dfs (grid,i-1,j)
            dfs (grid,i+1,j)
            dfs (grid,i,j-1)
            dfs (grid,i,j+1)
        num = 0
        for i in range(x):
            for j in range(y):
                if grid[i][j] == '1':
                    dfs(grid,i,j)
                    num += 1
        return num