深度优先搜索

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(n³)

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(n²) ：

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)
}