200. 岛屿数量

岛屿是指上下左右都是被0包起来的。使用递归的方式，也就是深度优先搜索，需要确定终止条件，也就是badcase是什么情况出现的。
二叉树是递到叶子节点的时候，因为下面是空子树了；矩阵就是越界，元素坐标不在这个矩阵里了，结合本题还要包括元素进海了。
**解题思路：**从左到右、从上到下依次遍历元素，对于每个元素，检查是否是陆地；如果是，那么就递归检查上下左右有没有陆地，这样就能找到该岛屿的所有部分，并且将其标记为已走过，这样根据岛屿的其中一个元素（最先被遍历到）就得到了这个岛屿存在，并且不会再重复计数。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # 判断空值情况
        if not grid: return 0
        # 初始化矩阵长宽
        rows, cols = len(grid), len(grid[0])
        # 初始化岛屿数量
        num = 0

        # 递归函数
        def dfs(r,c):
            # 如果走错了，返回空
            if r<0 or c<0 or r>=rows or c>=cols or grid[r][c]!='1':
                return 
            # 走到的，标记为走过
            grid[r][c] = '2'
            # 四处走走
            dfs(r-1, c) # 上
            dfs(r+1, c) # 下
            dfs(r, c-1) # 左
            dfs(r, c+1) # 右
        
        # 从左到右，从上到下，依次走过每个坐标
        for r in range(rows):
            for c in range(cols):
                # 如果当前是陆地，就递归遍历
                if grid[r][c] == '1':
                    dfs(r,c)
                    num += 1
        return num


            

695. 岛屿的最大面积

跟上一题类似，但是要维护一个全局变量——最大的岛屿面积。在每次递归，我们都计数，累加遍历到的1的次数。这样就每次遍历岛屿得到岛屿的面积，不断比较，得到最终结果。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:

        if not grid: return 0

        # 初始化
        rows, cols = len(grid), len(grid[0])
        max_area = 0

        def dfs(r, c):
            if r<0 or c<0 or r>=rows or c>=cols or grid[r][c]!=1: 
                return 0
            # 当前为1，计数
            temp = 1 
            grid[r][c] = 2 # 修改走过的
            # 检查相邻的
            temp += dfs(r-1,c)
            temp += dfs(r+1,c)
            temp += dfs(r,c-1)
            temp += dfs(r,c+1)

            return temp

        # 从左到右，从上到下，依次走过每个坐标
        for r in range(rows):
            for c in range(cols):
                # 如果当前是陆地，就递归遍历
                if grid[r][c] == 1:
                    max_area = max(dfs(r,c), max_area)

        return max_area

129. 求根节点到叶节点数字之和

每条路径的值都是上一层的结果10后加当前节点的值，因此递归主体可以确定为当前路径值10+当前节点值。
在遇到叶子节点时，就应该返回当前路径值。
如果不是叶子节点，需要往左右子树继续递归。
寻找到所有可能的路径和，加起来。

# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root: return 0

        # 递归，如果当前节点为空，则返回0
        def dfs(node, num):
            if not node:
                return 0
            # 不为空，则加上父节点的数*10
            num = num*10 + node.val
            # 如果左右子树均为空，则返回到该节点的总和
            if not node.left and not node.right: return num
            # 否则继续递归
            return dfs(node.left, num) + dfs(node.right, num)
        # 从根节点开始
        return dfs(root, 0)