Version: Next

深度优先搜索——DFS

主要应用：二叉树、图

  • 很多排列组合相关的问题，都可以通过 DFS 解决

引例 LeetCode 78.子集

  • 给定数列[1, 2, 3]，子集长度0, 1, 2, 3，返回所有可能的子集
子集长度子集
0[]
1[1], [2], [3]
2[1, 2], [1, 3], [2, 3]
3[1, 2, 3]

DFS法求解

  • 参考二叉树的前序遍历、中序遍历、后序遍历

image-20201207155815495

leetcode题目
  • 78.子集
  • 144.二叉树的前序遍历
  • 94.二叉树的中序遍历
  • 145.二叉树的后续遍历