【Leetcode刷题】【1142006951254】二叉树展开为链表，岛屿问题,岛屿的最大面积，岛屿周长

文章目录

114二叉树展开为链表题目描述 200岛屿问题题目描述 695岛屿的最大面积题目描述 1254封闭岛屿的数目题目描述思路 463岛屿的周长题目描述思路在网格上做DFS加上边界条件标记已遍历的岛屿，防止重复遍历求周长

114二叉树展开为链表

题目描述

这个题目乍一看，根据前面的思路，你可以能首先会选择前序遍历的方式来解决，是可以的，但是，比较麻烦，因为前序遍历的方式会改变右节点的指向，导致比较麻烦，那么，如果前序遍历不行，就考虑中序和后序遍历了，由于，在展开的时候，只需要去改变左右节点的指向，所以，这里其实最好的方式还是用后续遍历，既然是后续遍历，那么我们就可以快速的把后续遍历的框架写出来了。

public void flatten(TreeNode root) { if(root == null){ return; } flatten(root.left); flatten(root.right); //考虑当前一步做什么 }

我们这里要转变为链表，必然有一个左右指针的转换操作，我们从题目要求来看，链表是全部在右子树上，则转变过程应该采用深度遍历，遍历到一个根节点，然后把节点的右指针指向左子树，右子树用一个中间节点保存，然后左指针指向空，这样节点就全部在右子树上了，然后再看右指针指向的值是否为空，如果不为空，则让根节点变为右指针指向的结点，循环直到右指针指向的结点为空，然后把之前的右子树连接上，最后完成操作。

class Solution { public void flatten(TreeNode root) { if(root==null){ return; } flatten(root.left); flatten(root.right); TreeNode temp=root.right; root.right=root.left; root.left=null; while(root.right!=null){ root=root.right; } root.right=temp; } }

200岛屿问题

题目描述

我们可以看看这张图，黑色代表陆地，蓝色代表海洋，我们遍历可以利用二维数组，两重循环从第一行第一列开始遍历，一行一行，然后我们需要一个函数，判断是否为岛屿，并累加最后返回。

public int numIslands(char[][] grid) { int land=0; g=grid; for(int i=0;i<g.length;i++){ for(int j=0;j<g[i].length;j++){ if(g[i][j]=='0') continue; land+=sink(i,j); } } return land; }

所以接下来就是看sink函数，该函数的作用就是判断该点位置值是否为‘0’，若为‘0’，则表示没有岛屿，返回0，若不为0，则将该岛屿击沉（置为0），接着还要判断该点的左右上下四个方向的点是否全为海洋，依次递归，直到周围全为海洋（值全为0）

class Solution { int [] dx={-1,1,0,0};//两个数组凑成左右上下四个方向 int [] dy={0,0,1,-1}; char [][] g; public int numIslands(char[][] grid) { int land=0; g=grid; for(int i=0;i<g.length;i++){ for(int j=0;j<g[i].length;j++){ if(g[i][j]=='0') continue; land+=sink(i,j); } } return land; } public int sink(int i,int j){ if(g[i][j]=='0'){ return 0; } g[i][j]='0';//沉岛，遇到一个岛就沉一个，直到周围全部为水 for(int k=0;k<dx.length;k++){ int x=i+dx[k]; int y=j+dy[k]; if(x>=0&&x<g.length&&y>=0&&y<g[i].length){//判断坐标 (r, c) 是否在网格上 if(g[x][y]=='0') continue; sink(x,y); } } return 1; } }

695岛屿的最大面积

题目描述

有了上面的岛屿问题，大部分代码是一致的，我们复制过来稍加修改，要多定义一个变量count用来统计岛屿的面积，在沉岛函数sink中，我们每遇到一个值为1的点count加一，直到周边全为0后，这时就统计完一个岛的面积了，两重循环遍历就是为了遍历到每个岛，统计完一个岛的面积后存入res中，然后又开始新的岛面积统计，接着再与res比较，大的存入res中，最后统计完所有岛屿的面积，返回res.

class Solution { int [] dx={-1,1,0,0};//两个数组凑成左右上下四个方向 int [] dy={0,0,1,-1}; int [][] g; int count; public int numIslands(char[][] grid) { int land=0; g=grid; int res=0; for(int i=0;i<g.length;i++){ for(int j=0;j<g[i].length;j++){ if(g[i][j]==0) continue; count=0; sink(i,j); res=Math.max(res,count); } } return res; } public void sink(int i,int j){ if(g[i][j]==0){ return ; } g[i][j]=0;//沉岛，遇到一个岛就沉一个，直到周围全部为水 count++; for(int k=0;k<dx.length;k++){ int x=i+dx[k]; int y=j+dy[k]; if(x>=0&&x<g.length&&y>=0&&y<g[i].length){//判断坐标 (r, c) 是否在网格上 if(g[x][y]==0) continue; sink(x,y); } } } }

1254封闭岛屿的数目

题目描述

思路

这里主要是要抓住一个重点：

碰不到边缘的陆地才是孤岛

使用深度优先遍历； 所以一旦边界条件被满足，则直接返回false； 定下这个条件后，继续每遇到一个岛屿就沉岛，防止重复遍历，遇到海洋就返回true再继续从左右上下四个方向对于每一块陆地，向四面扩展，找到他的所有连接陆地，如果所有方向到最后都是海洋，则构成孤岛，数量+1

class Solution { public int closedIsland(int[][] grid) { int rows = grid.length; int cols = grid[0].length; int res= 0; for(int i = 1;i <rows;i++){ for(int j = 1;j <cols;j++){ if(grid[i][j] == 0){ if(dfs(grid,i,j)){//如果四面环水则res+1 res++; } } } } return res; } private boolean dfs(int[][] grid,int i ,int j){ int rows = grid.length; int cols = grid[0].length; if(i < 0 || j < 0 || i >=rows || j >= cols){//如果触碰到边界则不能构成孤岛，返回错误 return false; } if(grid[i][j] == 1){//遇到海洋则返回正确 return true; } grid[i][j] = 1;//遇到陆地则沉岛，变为海洋 //需要四面环水 boolean up = dfs(grid,i-1,j); boolean down = dfs(grid,i+1,j); boolean left = dfs(grid,i,j-1); boolean right = dfs(grid,i,j+1); if(up && down && left && right){ return true; } return false; } }

463岛屿的周长

题目描述

思路

在网格上做DFS

网格问题是这样一类搜索问题：有 m \times nm×n 个小方格，组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。这种题目乍一看可能有点麻烦，实际上非常简单，尤其是用 DFS 的方法。题目没有限制的话，我们尽量用 DFS 来写代码

// 基本的 DFS 框架：每次搜索四个相邻方格 void dfs(int[][] grid, int r, int c) { dfs(grid, r - 1, c); // 上边相邻 dfs(grid, r + 1, c); // 下边相邻 dfs(grid, r, c - 1); // 左边相邻 dfs(grid, r, c + 1); // 右边相邻 }

加上边界条件

我们这里采取先递归调用，再判断合法性，这里一个是不能超越边界，否则返回，还有遇到海洋也返回；

// 处理方格位于网格边缘的情况 void dfs(int[][] grid, int r, int c) { // 若坐标越界，直接返回 if (r<0&& r >=grid.length && c<0&& c >=grid[0].length)) { return; } // 若该方格不是岛屿，直接返回 if (grid[r][c] != 1) { return; } dfs(grid, r - 1, c); dfs(grid, r + 1, c); dfs(grid, r, c - 1); dfs(grid, r, c + 1); }

标记已遍历的岛屿，防止重复遍历

我们这里把遍历过的岛屿设置为2，根据情境不同，有些需要沉岛，

// 处理方格位于网格边缘的情况 void dfs(int[][] grid, int r, int c) { // 若坐标不合法，直接返回 if (!(0 <= r && r < grid.length && 0 <= c && c < grid[0].length)) { return; } // 若该方格不是岛屿，直接返回 if (grid[r][c] != 1) { return; } grid[r][c]=2;//表示已遍历 dfs(grid, r - 1, c); dfs(grid, r + 1, c); dfs(grid, r, c - 1); dfs(grid, r, c + 1); }

求周长

我们可以看到，当从一个岛屿方格走向边界网格，周长加一，走向海洋网格，周长也加一，所以

int dfs(int[][] grid, int r, int c) { // 若坐标不合法，直接返回 if (!(0 <= r && r < grid.length && 0 <= c && c < grid[0].length)) {//方格为边界，周长加一 return 1; } if(grid[r][c]==0){//方格为海洋，周长加一 return 1; } // 若该方格不是岛屿，直接返回 if (grid[r][c] != 1) { return 0; } grid[r][c]=2;//表示已遍历 dfs(grid, r - 1, c); dfs(grid, r + 1, c); dfs(grid, r, c - 1); dfs(grid, r, c + 1);

最后将上面所有结合，便得到最终代码：

public int islandPerimeter(int[][] grid) { for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 1) { // 题目限制只有一个岛屿，计算一个即可 return dfs(grid, i, j); } } } return 0;//若为空返回0 } public int dfs(int[][] grid, int r, int c) { if (!(0 <= r && r < grid.length && 0 <= c && c < grid[0].length)) { return 1; } if (grid[r][c] == 0) { return 1; } if (grid[r][c] != 1) { return 0; } grid[r][c] = 2; return dfs(grid, r - 1, c) + dfs(grid, r + 1, c) + dfs(grid, r, c - 1) + dfs(grid, r, c + 1); }