[TOC] ## DFS(Depth-First-Search) 深度优先 ### 方式一:前序遍历 ``` func preorderTraversal(root *TreeNode) []string { result := make([]string, 0) dfs(root, &result) return result } // V1：深度遍历，结果指针作为参数传入到函数内部 func dfs(root *TreeNode, result *[]string) { if root == nil { return } *result = append(*result, root.Data) dfs(root.Left, result) dfs(root.Right, result) } // 输出 // [A B D E C F] ``` ### 方式二: 分治法 ``` // V2：通过分治法遍历 func preorderTraversal(root *TreeNode) []string { result := divideAndConquer(root) return result } func divideAndConquer(root *TreeNode) []string { result := make([]string, 0) // 返回条件(null & leaf) if root == nil { return result } // 分治(Divide) left := divideAndConquer(root.Left) right := divideAndConquer(root.Right) // 合并结果(Conquer) result = append(result, root.Data) result = append(result, left...) result = append(result, right...) return result } // 输出 // [A B D E C F] ``` > DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并 ## 示例 ### 走格子 - 深度优先搜索的步骤分为 1.递归下去 2.回溯上来。 - 顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。 - 否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来    <details> <summary>main.go</summary> ``` package main import ( "fmt" "os" "os/exec" . "time" ) // 按照右下上左的方向顺序走 // 规则: // 1. 能走右边的走右边 // 2. 右边不行的下边 // 3. 下边不行的左右边 // 4. 左边不行的上(回溯) /** [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 2 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] */ const ( n = 10 // 长=y m = 10 // 宽=x ) type dfsMap struct { goal_x int goal_y int // //目标的坐标，暂时设置为右下角 graph [n][m]int used [n][m]int px, py [4]int // 通过px 和 py数组来实现左下右上的移动顺序 flag bool cout int // 计数 走了多久 } func newDfsMap(goal_x int, goal_y int) *dfsMap { d := dfsMap{ goal_x: goal_x, goal_y: goal_y, // 右下上左 // px+py 可指定四个方向 // x 加方向为右 // y 加方向为下 px: [4]int{1, 0, 0, -1}, py: [4]int{0, 1, -1, 0}, // 下上右下 //px: [4]int{0, 0, 1, -1}, //py: [4]int{1, -1, 0, 0}, } d.graph[goal_y][goal_x]=2 return &d } func (d *dfsMap) Dfs() { d.dfs(0,0) } func (d *dfsMap) dfs(y int ,x int){ Sleep(100* Millisecond) d.clear() fmt.Printf("%s", d) // or if x==d.goal_x && y==d.goal_y { if d.graph[y][x] == d.graph[d.goal_y][d.goal_x] { d.flag = true fmt.Printf("走了 %+v 步\n", d.cout ) return } // 遍历四个方向 for i := 0; i < 4; i++ { new_x := x + d.px[i] new_y := y + d.py[i] if new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && d.used[new_y][new_x] == 0 && !d.flag { d.used[new_y][new_x] = 1 // //将该格子设为走过 d.cout++ // 记步数 d.dfs(new_y, new_x) // //递归下去 d.used[new_y][new_x] = 0 // //状态回溯，退回来，将格子设置为未走过 } } } func (d *dfsMap) clear() { cmd := exec.Command("clear") cmd.Stdout = os.Stdout cmd.Run() } func (d *dfsMap) String()string{ var res string tmp :=d.used tmp[d.goal_y][d.goal_x]=d.graph[d.goal_y][d.goal_x] for i:=0; i<n; i++ { res+=fmt.Sprintf("%v",tmp[i])+"\n" } return res } func main() { d := newDfsMap(5, 3) d.Dfs() } ``` </details> <br />