leetcode 797. 所有可能的路径 [递归vs非递归]

深碍√TFBOYSˉ_ 2022-11-05 13:57 153阅读 0赞

**递归**

class Solution { 
    public:
        
        vector<vector<int>> ret;
        vector<vector<int>> g;
        vector<int> vi;
        vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& g) { 
            this->g = g;
            int n = g.size();
            vi = vector<int> (n,0);
            dfs(0,n-1,{ });
            return ret;
        }
        
        bool dfs(int a, int b,vector<int> t){ 
            if(a==b){ 
                t.push_back(a);
                ret.push_back(t);
                return true;
            }else{ 
                
                vi[a] = 1;
                t.push_back(a);
                for(int n:g[a]){ 
                    if( !vi[n] ){ 
                        dfs(n,b,t);
                        vi[n] = 0;
                    }
                }
                
            }
            return true;
        }
    };

![在这里插入图片描述][20210306214702259.png]

**非递归**  
**需要记录一下遍历到了栈顶节点的第几个后继**

#define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
        
        vector<vector<int>> ret;
        vector<int> vi;
        vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& g) { 
            
            int n = g.size();
            vi = vector<int> (n,0);
            vector<int> chno(n,0);
            stack<int> st;
            
            vector<int> t;
            
            vi[0] = 1;
            t.push_back(0);
            st.push(0);
            
            while(st.size() > 0){ 
                
                int cur = chno[st.top()] ;
                if(cur < g[st.top()].size()){ 
                    chno[st.top()]++;
                    //debug(chno[0])
                    int nc = g[st.top()][cur];
                    //debug(nc)
                    if(!vi[ nc ]){ 
                        vi[ nc ] = 1;
                        st.push(nc);
                        t.push_back(nc);
                        if( nc == n-1){ 
                            ret.push_back(t);   
                        }
                    }
                    
                }else{ 
                    vi[st.top()] =  0;
                    chno[st.top()] = 0;
                    //debug(st.top())
                    st.pop();
                    t.pop_back();
                }
                
                
            }
            
            return ret;
        }
    
    };

![在这里插入图片描述][20210306214441634.png]

[20210306214702259.png]: /images/20221023/9f5e190da3e04f529eb030bfadc085d7.png
[20210306214441634.png]: /images/20221023/f4fccbcd069a45f1b68b0e18c12d422f.png