图的遍历一般都需要一个visit数组避免环路不停的走，死循环。如果明确了没环，那就不需要考虑visit数组判重了。

树也是一种特殊的图

1. All Paths From Source to Target

很典型的图的遍历题，用dfs来做，首先题(i.e., there will be no self-loops). 没有自环，那可以省去visit数组判重。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    Map<Integer, List<Integer>> g = new HashMap<>();
    int n;
    int[][] graph;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        this.graph = graph;
        List<Integer> path = new ArrayList<>();
        n = graph.length;
        dfs(0, path);
        return res;
    }

    public void dfs(int root, List<Integer> path){
        path.add(root);
        if(root == n - 1){
            res.add(new ArrayList<>(path));
            //path.remove(path.size() - 1);
            //return;  这道题可以省去这一步判断的原因是当你找到target的时候，target一定是最后一个节点，他后
            //面没有点了，所以他也会执行完，图的遍历模板其实要加上这两个判断，这样如果target有后继节点也不
            //再往后执行
        }
        for(int i : graph[root]){
            dfs(i, path);
        }
        path.remove(path.size() - 1);
    }
}

这里 path.add() 要在for循环外面进行，以及回溯
如果是 有自环，需要判重的，图的遍历的模板就要加上对visit的判断

```
public void dfs(int root, List[HTML_REMOVED] path){
if(visit[root]) return;
visit[root] = true;
path.add(root);//一定要在判断条件的前面进行path.add
if(root == n - 1){
res.add(new ArrayList<>(path));
//path.remove(path.size() - 1);
//return; 这道题可以省去这一步判断的原因是当你找到target的时候，target一定是最后一个节点，他后
//面没有点了，所以他也会执行完，图的遍历模板其实要加上这两个判断，这样如果target有后继节点也不
//再往后执行
}

    for(int i : graph[root]){
        dfs(i, path);
    }
    path.remove(path.size() - 1);
}

```

树的遍历，树就是一种特殊的图
树的遍历，一般就是特殊判断root == null return null 走过子节点
如果要找到子节点的路径，特殊判断一下当root.left == null && root.right == null 时候
然后分别再遍历left，right