DFS

Depth-first search：

  • 重点考虑以什么顺序进行搜索；
    • 搜索流程是树，画出树有助于解题。
  • 深度优先，无论走哪条路都要走到头，一旦走到头，不是直接回到头，而是边回去边看能否继续往前走（回溯）；
    • 递归写法在递归调用过程中有自动创建的调用栈，迭代写法要手动管理栈。
  • 使用栈；
  • 空间和树的高度（路径上点的个数）成正比，O(h)，空间上有优势；
  • 第一次搜到的点不具有“最短路”的性质。

实现要点：

  • 没有常用的代码框架；
  • 回溯后（一次递归结束）要及时恢复现场；
  • 剪枝：提前就可以判断出不合法或不是最优解，无需继续往下搜。

数的全排列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

var n int // 一共的层数
var path []int
var used []bool

func dfs(idx int) {
    // 达到了全排列的长度，输出结果
    if idx == n {
        for _, ele := range path {
            fmt.Printf("%d ", ele)
        }
        fmt.Println()
        return
    }
    
    for i := 1; i <= n; i++ {
        if !used[i] {
            path[idx] = i
            used[i] = true
            dfs(idx+1)
            // 回溯，恢复现场
            used[i] = false
            path[idx] = 0 // 可以不写，会被 path[idx] = i 更新掉，不会有脏数据
        }
    }
}

func main() {
    fmt.Scanf("%d", &n)
    path = make([]int, n)
    used = make([]bool, n+1)
    
    dfs(0) // 从第 0 层开始搜索，一共搜搜到 n-1 层
}

path sum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    
    if root.Left == nil && root.Right == nil { // 叶子节点
        return root.Val == targetSum    
    }
    
    if hasPathSum(root.Left, targetSum - root.Val) {
        return true
    }
    if hasPathSum(root.Right, targetSum - root.Val) {
        return true
    }
    
    return false
}

References