1、简介
DFS（Depth-First-Search）：深度优先搜索。从一个初始结点开始，沿着一条路一直走到底，如果不是目标解，就返回到上一个结点，从另一条路开始走到底，使用了回溯的思想。
2、应用
（1）二叉树的层序遍历
下面是 Go 语言版的完整代码，可运行：
package main
import (
"fmt"
"container/list"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func dfs(node *TreeNode, result *[][]int, level int) {
if len(*result) < level + 1 {
*result = append(*result, []int{} )
}
(*result)[level] = append( (*result)[level], node.Val )
if nil != node.Left{
dfs(node.Left, result, level+1)
}
if nil != node.Right{
dfs(node.Right, result, level+1)
}
}
func levelOrderDFS(root *TreeNode) [][]int {
if nil == root{
return [][]int{}
}
result := [][]int{}
dfs(root, &result, 0)
return result
}
func createBST( v []int ) *TreeNode {
n := len(v)
if n == 0{
return nil
}else if n == 1{
return & TreeNode{ v[0], nil, nil}
}
m := n/2
root := & TreeNode{ v[m], nil, nil}
root.Left = createBST( v[0:m] )
root.Right = createBST( v[m+1:] )
return root
}
func main() {
tree := createBST( []int {1,2,3,4,5,6,7} )
fmt.Println(levelOrderDFS(tree))
}
（2）二叉树的最大深度
某个结点的最大深度，可以先求出左子树的最大深度和右子树的最大深度中较大的那一个，再加上 1 即可。递归的结束条件是遇到空结点，返回 0 。
func maxDepthDFS(root *TreeNode) int {
if root == nil{
return 0
}
max := maxDepthDFS(root.Left)
right := maxDepthDFS(root.Right)
if right > max{
max = right
}
return 1 + max
}
（3）二叉树的最小深度：
func minDepthDFS(root *TreeNode) int {
if root == nil{
return 0
}
min := minDepthDFS(root.Left)
right := minDepthDFS(root.Right)
if right < min{
min = right
}
return 1 + min
}
（4）解数独
(A) 判断数独是否有效，暴力破解
一个简单的解决方案是 遍历该 9 x 9 数独，以确保：
行中没有重复的数字，
列中没有重复的数字，
3 x 3 子数独内没有重复的数字。
完整代码如下，外围 2 层循环，加上 isLegal 函数内的 1 层循环，时间复杂度是 O(n3)
package main
import "fmt"
func isValid(board *[][]byte, row int, col int) bool {
for i:=0 ; i < 9; i++ {
if (*board)[i][col] == (*board)[row][col] && i != row {
return false
}
if (*board)[row][i] == (*board)[row][col] && i != col {
return false
}
r := row / 3 * 3 + i / 3
c := col / 3 * 3 + i % 3
if (*board)[r][c] == (*board)[row][col] && r != row && c != row {
return false
}
}
return true
}
func isValidSudoku(board [][]byte) bool {
for i:=0 ; i < 9; i++ {
for j:=0 ; j < 9; j++ {
if board[i][j] == '.' || isValid(&board, i , j) {
continue
}
return false
}
}
return true
}
func main() {
input := [][]byte{
{'5','3','.','.','7','.','.','.','.'},
{'6','.','.','1','9','5','.','.','.'},
{'.','9','8','.','.','.','.','6','.'},
{'8','.','.','.','6','.','.','.','3'},
{'4','.','.','8','.','3','.','.','1'},
{'7','.','.','.','2','.','.','.','6'},
{'.','6','.','.','.','.','2','8','.'},
{'.','.','.','4','1','9','.','.','5'},
{'.','.','.','.','8','.','.','7','9'} }
fmt.Println(isValidSudoku(input))
}
(B) 判断数独是否有效--空间换时间
先用数组或哈希表把状态保存起来，这样在判重的时候时间复杂度是 O(1)，总的时间复杂度是 O(n2) ：
func isValidSudoku(board [][]byte) bool {
x := [9][9]bool{}
y := [9][9]bool{}
box := [3][3][9]bool{}
for i:=0 ; i < 9; i++ {
for j:=0 ; j < 9; j++ {
if board[i][j] == '.' {
continue
}
bx := i/3
by := j/3
n := board[i][j] - '1'
if true == x[i][n] || true == y[j][n] || true == box[bx][by][n] {
return false
}
x[i][n] = true
y[j][n] = true
box[bx][by][n] = true
}
}
return true
}
(C) 解数独
先用数组或哈希表把状态保存起来，遍历每个空格，for 循环遍历 9 个数字，调用 couldPlace() 方法来判断，如果某个格子可以放该数字，就调用 placeNumber() 方法来更新状态 ，调用 placeNextNumbers() 方法继续下一个格子，如果这条路走不通，就再调用 removeNumber() 方法清除刚才的状态。直到找出解。
package main
import "fmt"
const (
n = 3
N = n*n
)
type Sudoku struct {
rows [N][N]bool
columns [N][N]bool
boxes [N][N]bool
success bool
pBoard *[][]byte
}
func (this *Sudoku) couldPlace(d int, row int, col int) bool {
idx := (row / n ) * n + col / n;
return !( this.rows[row][d] || this.columns[col][d] || this.boxes[idx][d] )
}
func (this *Sudoku) placeNumber(d int, row int, col int) {
idx := (row / n ) * n + col / n
this.rows[row][d] = true
this.columns[col][d] = true
this.boxes[idx][d] = true
(*this.pBoard)[row][col] = byte(d + '1')
}
func (this *Sudoku) removeNumber(d int, row int, col int) {
idx := (row / n ) * n + col / n
this.rows[row][d] = false
this.columns[col][d] = false
this.boxes[idx][d] = false
(*this.pBoard)[row][col] = '.'
}
func (this *Sudoku) placeNextNumbers(row int, col int) {
if col == N-1 && row == N-1 {
this.success = true
} else {
if col == N-1 {
this.dfs(row + 1, 0)
} else {
this.dfs(row , col + 1)
}
}
}
func (this *Sudoku) dfs(row int, col int) {
if (*this.pBoard)[row][col] == '.' {
for i := 0; i < N; i++ {
if true == this.couldPlace(i, row, col) {
this.placeNumber(i, row, col)
this.placeNextNumbers(row, col)
if false == this.success {
this.removeNumber(i, row, col)
}
}
}
} else {
this.placeNextNumbers(row, col)
}
}
func (this *Sudoku) init_array() {
for i := 0; i < N; i++ {
for j := 0; j < N; j++ {
num := (*this.pBoard)[i][j]
if num != '.' {
d := num - '1'
this.placeNumber( int(d), i, j)
}
}
}
}
func solveSudoku(board [][]byte) {
p := Sudoku{pBoard: &board}
p.init_array()
p.dfs(0, 0)
}
func printSudoku(board [][]byte) {
fmt.Println()
for i := 0; i < N; i++ {
for j := 0; j < N; j++ {
fmt.Printf( "%c ", board[i][j])
}
fmt.Println()
}
fmt.Println()
}
func main() {
input := [][]byte{
{'5','3','.','.','7','.','.','.','.'},
{'6','.','.','1','9','5','.','.','.'},
{'.','9','8','.','.','.','.','6','.'},
{'8','.','.','.','6','.','.','.','3'},
{'4','.','.','8','.','3','.','.','1'},
{'7','.','.','.','2','.','.','.','6'},
{'.','6','.','.','.','.','2','8','.'},
{'.','.','.','4','1','9','.','.','5'},
{'.','.','.','.','8','.','.','7','9'} }
printSudoku(input)
solveSudoku(input)
printSudoku(input)
}
网友评论