DFS 深度优先
最后更新于：2022-04-02 04:22:27
[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.回溯上来。
- 顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。
- 否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来
';