脚本宝典收集整理的这篇文章主要介绍了【leetcode】797. All Paths From Source to Target，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

　　Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

　　Example 1:

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.　　这道题的需求就是从0节点开始依次遍历到最后一个节点，并求出所有的路径，为了求出所有的路径一般选择递归的方式，而且这题的数据没有节点遍历的死循环（即0->1 1->0）,所有节点都会指向下一个不重复的节点，这样就需要额外的判断了。    递归终止条件就是检索到最后一个节点，然后把路径记录下来。

class Solution {
private:
    int end=0;
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        // 记录所有的paths 利用递归
        // 所有路径都从0节点开始
        // 在每个节点中循环去寻找下一个节点 最终如果找到end节点 则退出
        end=graph.size()-1;
        vector<vector<int>> res;
        vector<int> dp;
        digui(0,res,dp,graph);
        return res;
        
    }
    void digui(int point,vector<vector<int>>&res,vector<int>dp,vector<vector<int>>& graph)
    {
        dp.push_back(point); //填充当前节点
        if(point==end){
            res.push_back(dp);
            return;
        }
        vector<int> nums=graph[point];
        for(auto nn:nums){
            digui(nn,res,dp,graph); 
        }
        return;
        
    }
};

脚本宝典总结

以上是脚本宝典为你收集整理的【leetcode】797. All Paths From Source to Target全部内容，希望文章能够帮你解决【leetcode】797. All Paths From Source to Target所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。