上一篇文章我们讲了 DFS 的理论部分，现在来看一道例题。
例子
剑指Offer 55 - I
二叉树的深度
题目：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
给定二叉树[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回最大深度为 3。
这个题其实直接可以用层次遍历（BFS）解决，但 DFS 同样可以解决
思路
我们用 DFS分别遍历左右子树的深度，两者间取最大值即为此数的最大深度
当根节点为空时我们返回 0：
if(root==null) return0;
不为空的时候，我们遍历左子树的深度：
int leftDepth = maxDepth(root.left);
再遍历右子树的深度：
intrightDepth=maxDepth(root.right);
最后我们取左右子树深度的最大值：
returnMath.max(left+1, right+1); //因为root根节点算第一层，所以最后加1
代码
我们给出完整代码：
classSolution {
publicintmaxDepth(TreeNoderoot) {
if(root==null){
return0;
}
intleft=maxDepth(root.left);
intright=maxDepth(root.right);
returnMath.max(left+1, right+1);
}
}
请注意：当节点不为空时，我们每次递归的maxDepth最后返回的是 Math.max(left + 1, right + 1) 而不是 0。
上述代码也可以合并如下：
classSolution {
publicintmaxDepth(TreeNoderoot) {
if(root==null) return0;
returnMath.max(maxDepth(root.left), maxDepth(root.right)) +1;
}
}
剑指Offer 55 - II
平衡二叉树
题目：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/\
9 20
/ \
15 7
返回 true。
有了上一个题的基础，这个题思路很好想到。
思路
我们用上一题的 Depth 函数分别求出左右子树的深度
- 并判断他们的差值是否小于等于 1（平衡条件）
- 再判断左右子树分别是否满足平衡
满足上述条件，则整棵树平衡
代码
完整代码：
classSolution {
publicbooleanisBalanced(TreeNoderoot) {
if (root==null) returntrue;
intgap=Math.abs(depth(root.left) -depth(root.right)); //左右子树深度差额绝对值
return gap<=1&&isBalanced(root.left) &&isBalanced(root.right);
}
privateintdepth(TreeNoderoot) {
if (root==null) return0;
returnMath.max(depth(root.left), depth(root.right)) +1;
}
}
因为递归实现 DFS 比栈简洁方便，所以大部分 DFS 都是通过递归实现。
热完身下面我们开始来点正菜。
LeetCode 695
岛屿最大面积
题目：给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 )
示例 1:
[[0,0,1,0,0,0,1,1],
[0,0,0,0,0,0,1,1],
[0,1,1,0,1,0,0,0]]
对于上边这个矩阵应返回 4（左上角）。
思路
我们考虑用DFS的思想，即从某块岛屿出发
- 如果此块岛屿为 0（不是陆地），则跳过，开始遍历下一块岛屿
- 如果此块岛屿为 1（是陆地），则计数器加 1 ，并开始遍历它的上下左右临近的岛屿，并将此块岛屿置 0 （保证每块陆地只被遍历一遍，避免重复遍历）
是 DFS 那么大可能离不开递归，此题我们首先定义出一个 dfs 的递归函数：
intdfs(int[][] grid, inti, intj);
参数为 grid 二维数组和 i , j 两个整数，那么 grid[i] [j] 即可遍历到某块岛屿。
我们考虑递归的边界条件，递归的边界条件应该是什么呢？即 grid[i] [j] 什么时候是非法的？
因为我们在遍历到某块陆地的时候，我们要紧接着递归遍历它的上下左右岛屿，考虑grid[i] [j]临近的上下左右的岛屿应该如何表示呢？
我们可以得出：
- grid[i - 1] [j] 为上岛屿
- grid[i + 1] [j] 为下岛屿
- grid[i] [j - 1] 为左岛屿
- grid[i] [j + 1] 为右岛屿
那么递归函数的参数什么时候非法呢？
i - 1 和 j - 1 不能减到小于 0
- 即当 i < 0 或 j < 0，非法
i + 1 和 j + 1不能增大到超过数组大小
- 即当 i == grid.length 或 j == grid[i].length，非法
并且当grid[i] [j] == 0 ，即此块岛屿不是陆地时返回 0
即：
if (i<0||j<0||i==grid.length||j==grid[i].length||grid[i][j] ==0)
return0;
现在我们找到了dfs递归函数的边界。
按照最开始的算法思路，现在我们应该处理当当前岛屿为陆地时的情况：
- 如果此块岛屿为 1（是陆地），则计数器加 1 ，并开始遍历它的上下左右临近的岛屿，并将此块岛屿置 0 （保证每块陆地只被遍历一遍，避免重复遍历）
当前岛屿若为 1 （为陆地），我们将这块陆地置为 0
并且递归遍历此块岛屿的上下左右临近岛屿，返回递归结果并加 1（计数器加 1）
即：
grid[i][j] =0;
returndfs(grid, i-1, j) +dfs(grid, i+1, j) +dfs(grid, i, j-1) +dfs(grid, i, j+1) +1;
此时，我们的递归函数内容就写完了。
我们回到主函数：
publicintmaxAreaOfIsland(int[][] grid);
主函数的内容就很好写了。
我们初始化一个变量为 0 （若给定矩阵全为 0 ，没有一块陆地，则返回 0）：
intres=0;
dfs递归函数找出了每一部分陆地的面积大小，我们只需要在这些陆地当中，选取一个面积最大的即可：
Math.max(res, dfs(grid, i, j));
主函数里我们只需要两层 for 循环，来遍历二维数组对应的每个元素 ：
for (inti=0; i<grid.length; i++) {
for (intj=0; j<grid[i].length; j++) {
...
}
}
代码
由上我们即写出了整个代码，贴出完整代码：
classSolution{
publicintmaxAreaOfIsland(int[][] grid){
intres=0;
for (inti=0; i<grid.length; i++){
for (intj=0; j<grid[i].length; j++){
res=Math.max(res,dfs(grid,i,j));
}
}
returnres;
}
privateintdfs(int[][] grid, inti, intj){
if (i<0||j<0||i==grid.length||j==grid[i].length||grid[i][j] ==0)
return0;
grid[i][j] =0;
returndfs(grid, i-1, j) +dfs(grid, i+1, j) +dfs(grid, i, j-1) + dfs(grid, i, j+1) +1;
}
}
这是一道 Medium 题目
其实理解了 dfs 递归的思想，找到了递归函数的边界，再结合题目本身的条件，其实不难做出来。
那今天的内容就先到这里啦~
