CodeArena

本篇记录一下Golang如何实现深度优先搜索【DFS】和广度优先搜索【BFS】两种算法。

BFS

1
package main
2

3
import "fmt"
4

5
type TreeNode struct {
6
  Val   int
7
  Left  *TreeNode
8
  Right *TreeNode
9
}
10

11
type Queue []*TreeNode
12

13
// 入队方法
14
func (q *Queue) Enqueue(n *TreeNode) {
15
  if n == nil {
33 collapsed lines
16
    return
17
  }
18
  *q = append(*q, n)
19
}
20

21
// 出队方法
22
func (q *Queue) Dequeue() *TreeNode {
23
  n := (*q)[0]
24
  *q = (*q)[1:]
25
  return n
26
}
27

28
// 广度优先遍历 BFS
29
func BFS(root *TreeNode) {
30
  q := Queue{}
31
  q.Enqueue(root)
32

33
  for len(q) > 0 {
34
    n := q.Dequeue()
35
    fmt.Println(n.Val)
36
    q.Enqueue(n.Left)
37
    q.Enqueue(n.Right)
38
  }
39
}
40

41
func main() {
42
  root := TreeNode{
43
    Val:   1,
44
    Left:  &TreeNode{Val: 2, Right: &TreeNode{Val: 4}},
45
    Right: &TreeNode{Val: 3, Right: &TreeNode{Val: 5}},
46
  }
47
  BFS(&root)
48
}

广度优先遍历也叫层序遍历，需要借助一个队列来实现，在遇到岔路口时我们需要把所有的选择记录下来即入队操作

DFS

深度优先遍历 DFS 包括三种算法：前序遍历，中序遍历和后序遍历

可以采用递归实现：

1
// 深度优先遍历 DFS
2
func DFS(root *TreeNode) {
3
  if root == nil {
4
    return
5
  }
6

7
  fmt.Println(root.Val)
8

9
  // 左子树
10
  DFS(root.Left)
11
  // 右子树
12
  DFS(root.Right)
13
}

DFS和BFS算法

BFS

DFS