DFS深度优先搜索

发表于 更新于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

DFS深度优先搜索

深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.

深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

基本思路

深度优先遍历图的方法是，从图中某顶点v出发：

（1）访问顶点v； （2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。　

解决 JZ34 二叉树中和为某一值的路径(二)

题目链接

根节点开始向左右子树进行递归，由于要返回具体的路径，递归函数中需要处理的是：

  1. 当前的路径path要更新
  2. 当前的目标值expectNumber要迭代，减去当前节点的值
  3. 若当前节点是叶子节点，考虑是否满足路径的期待值，并考虑是否将路径添加到返回列表中（和之前二叉树中和为某一值的路径(一)不同需要加入返回列表）

tips：下面回溯与之前一般的分治解决问题的区别在于，使用了全局变量保留路径(当然也可以借助传引用保留，主要是要跨递归不能是局部变量）。且会有清理全局变量即清理现场的操作。

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
34
35
36
37
38
39
40
41
42
43
44
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <cstdio>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param target int整型 
     * @return int整型vector<vector<>>
     */
    vector<int> path;
    vector<vector<int> > FindPath(TreeNode* root, int target) {
        // write code here
         vector<vector<int> > ret;
         if(root==nullptr)
             return ret;
         dfs(ret,root,target);
         return ret;
    }
    void dfs(vector<vector<int> > &retpaths,TreeNode* root, int target){
        //判断是否满足要求
        target-=root->val;
        path.emplace_back(root->val);
         if(root->left==nullptr&&root->right==nullptr&& target==0){
            retpaths.push_back(path);
            //return; 这里不能return不然后面就没法path pop掉这一层的结点。也可以在上面加一个pathpopback然后再return
         }
         if(root->left!=nullptr)
            dfs(retpaths,root->left,target);
         if(root->right!=nullptr)
            dfs(retpaths,root->right,target);
        path.pop_back();
    }

};