广度优先搜索

1、简介
BFS（Breadth-First-Search）：广度优先搜索，也叫宽度优先搜索。是一种“地毯式”层层推进的搜索策略，即先查找离起始结点最近的，然后是次近的，再依次往外查找，比较符合人的思维。

把初始结点放入队列中，取队列长度 len，执行循环 len 次：
每次从队列首位取出一个结点，把它下一层的结点加入队列的末尾，
并更新 len 的值，len 的值代表每一层的节点个数，
重复上述的步骤，直到没有新的结点为止。

如果是图，需要一个 Set （通常命名为 visited）来保存已经被访问过的结点，防止回路；
如果是树则不需要。

2、应用
（1）二叉树的层序遍历
下面是 Go 语言版的完整代码，可运行：

package main

import (
"fmt"
"container/list"
)

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func levelOrderBFS(root *TreeNode) [][]int {
    if nil == root{
        return [][]int{}
    }

    result := [][]int{}
    queue := list.New()
    queue.PushBack(root)

    for level_size := 1; level_size > 0; level_size = queue.Len() {
        current_level := make( []int, 0, level_size)

        for i:=0; i < level_size; i++ {
            element := queue.Front()
            node := element.Value.(*TreeNode)
            queue.Remove(element)

            current_level = append(current_level, node.Val)

            if node.Left != nil{
                queue.PushBack(node.Left)
            }
            if node.Right != nil{
                queue.PushBack(node.Right)
            }
        }
        result = append(result, current_level)
    }
    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(levelOrderBFS(tree))
}

（2）二叉树的最大深度
用一个变量来记录深度，每遍历一层就自增 1，直到没有新的结点为止：

func maxDepthBFS(root *TreeNode) int {
    if nil == root{
        return 0
    }
    result := 0
    queue := list.New()
    queue.PushBack(root)

    for level_size := 1; level_size > 0; level_size = queue.Len() {
        result++
        for i:=0; i < level_size; i++ {
            element := queue.Front()
            queue.Remove(element)
            node := element.Value.(*TreeNode)
            if node.Left != nil {
                queue.PushBack(node.Left)
            }
            if node.Right != nil {
                queue.PushBack(node.Right)
            }
        }
    }
    return result
}

（3）二叉树的最小深度
用一个变量来记录深度，每遍历一层就自增 1，遇到空节点即可返回：

func minDepthBFS(root *TreeNode) int {
    if nil == root{
        return 0
    }
    result := 0
    queue := list.New()
    queue.PushBack(root)

    for level_size := 1; level_size > 0; level_size = queue.Len() {
        result++
        for i:=0; i < level_size; i++ {
            element := queue.Front()
            node := element.Value.(*TreeNode)
            queue.Remove(element)
            if node.Left == nil || node.Right == nil {
                return result
            }
            queue.PushBack(node.Left)
            queue.PushBack(node.Right)
        }
    }
    return result
}