DFS

1254. 统计封闭岛屿的数目

func closedIsland(grid [][]int) int {
	var num int
	for i:=0; i<len(grid); i++ {
		for j:=0; j<len(grid[0]); j++ {
			if grid[i][j] == 0 && dfs(grid, i, j) {
				num += 1
			}
		}
	}
	return num
}


func dfs(grid [][]int, i, j int) bool {
	if i == len(grid) || j == len(grid[0]) || i < 0 || j < 0 {
		return false
	}

	if grid[i][j] == 1 {
		return true
	}

	grid[i][j] = 1

	a := dfs(grid, i-1, j)
	b := dfs(grid, i+1, j)
	c := dfs(grid, i, j-1)
	d := dfs(grid, i, j+1)
	if a && b && c && d {
		return true
	}
	return false
}

695. 岛屿的最大面积

func maxAreaOfIsland(grid [][]int) int {
    res := 0
    for i:=0; i<len(grid); i++ {
        for j:=0; j<len(grid[0]); j++ {
            if grid[i][j] == 1 { 
                res = max(res,dfs(grid, i, j))
            }   
        }   
    }   
    return res 
}

func dfs(arr [][]int, i, j int) int {
    if i < 0 || j < 0 || i == len(arr) || j == len(arr[0]) ||arr[i][j] == 0 { 
        return 0
    }   

    arr[i][j] = 0 

    nums := 1                                                                                                                                                           
    nums += dfs(arr, i-1, j)
    nums += dfs(arr, i+1, j)
    nums += dfs(arr, i, j-1)
    nums += dfs(arr, i, j+1)
    return nums 
}

func max(i, j int) int {
    if i > j { 
        return i
    }   
    return j
}

200. 岛屿数量

func numIslands(grid [][]byte) int {
    isLandNum := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                infect(grid, i, j)
                isLandNum++
            }
        }
    }
    return isLandNum
}

func infect(grid [][]byte, i, j int) {
    if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) || grid[i][j] != '1' {
        return
    }
    grid[i][j] = '2'
    infect(grid, i+1, j)
    infect(grid, i-1, j)
    infect(grid, i, j+1)
    infect(grid, i, j-1)
}

113. 二叉树路径和

var res [][]int
func pathSum(root *TreeNode, sum int) [][]int {
	res = [][]int{}
	dfs(root, sum, []int{})
	return res
}

func dfs(root *TreeNode, sum int, stack []int) {
	if root == nil {
		return
	}
	stack = append(stack, root.Val)
	if root.Left == nil && root.Right == nil {
		if sum == root.Val {
			r := make([]int, len(stack))
			copy(r, stack)
			res = append(res, r)
		}
	}
	dfs(root.Left, sum-root.Val, stack)
	dfs(root.Right, sum-root.Val, stack)
}

114. 二叉树展开为链表

func flatten(root *TreeNode)  {
    if root == nil {
        return 
    }
    flatten(root.Left)
    flatten(root.Right)

    temp := root.Right

    root.Right, root.Left = root.Left, nil

    for root.Right != nil {
        root = root.Right
    }

    root.Right = temp 
}