题解 | #路径数目#

思路：

题目的主要信息：

一棵以1为根节点的树，节点值为0或者1
最多经过两个值为1的节点的情况下，求有多少条从根达到叶结点的路径

方法一：dfs
具体做法：
我们首先根据题目给出的边信息构建邻接矩阵，可以访问某个节点的所有相邻节点。
然后从根节点开始dfs递归，递归过程不断更新路径中1的数量count变量，只有count小于等于2才能继续遍历下去，维护答案。

class Solution {
public:
    //dfs函数，其中cur是当前节点，pre是这个节点遍历过来的前序节点，count记录经过多少节点值为1
    void dfs(int cur, int pre, int count, int& res, vector<int>& f, vector<vector<int>>& G){
        if(f[cur - 1])
            count++; //首先判断这条路径经历的1数
        if(count > 2)
            return;
        bool flag = true; //判断是否是叶子
        for(int i = 0; i < G[cur].size(); i++){ //按照所有的相邻节点深度递归
            if(G[cur][i] != pre){ //不能遍历前序节点
                flag = false;
                dfs(G[cur][i], cur, count, res, f, G);
            }
        }
        if(flag) //能往下走才加路径数1
            res++;
    }
    int solve(int n, vector<Point>& Edge, vector<int>& f) {
        int res = 0;
        vector<vector<int> > G(n + 1);
        for(int i = 0; i < Edge.size(); i++){ //构建图
            G[Edge[i].x].push_back(Edge[i].y);
            G[Edge[i].y].push_back(Edge[i].x);
        }
        dfs(1, 0, 0, res, f, G); //深度优先遍历
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，遍历每一个节点
空间复杂度： $O(n)$ ，辅助矩阵G最多有 $2n$ 个元素

方法二：bfs
具体做法：
我们也可以利用bfs的方法遍历每一个节点。借助队列进行bfs，但是我们需要记录每个前序节点到后续节点时的经过的节点值为1的数量，因此我们队列中记录的是一个pair结构，其first记录节点序号，second记录方法一中的count，bfs的时候每个节点判断是否是叶子，到达叶子时如果count还是不超过2，则路径数增加。
图片说明

class Solution {
public:
    int solve(int n, vector<Point>& Edge, vector<int>& f) {
        int res = 0;
        vector<vector<int> > G(n + 1);
        for(int i = 0; i < Edge.size(); i++){ //构建图
            G[Edge[i].x].push_back(Edge[i].y);
            G[Edge[i].y].push_back(Edge[i].x);
        }
        vector<bool> vis(n + 1, false); //节点是否被访问过
        vis[1] = true;
        queue<pair<int, int> > q; //队列中分别记录节点号和经历的节点值1的个数
        q.push(make_pair(1, 0)); //根节点入队
        while(!q.empty()){ //bfs
            int cur = q.front().first;
            int count = q.front().second;
            q.pop();
            if(f[cur - 1])
                count++;
            bool flag = true;  //判断是否是叶子
            for(int i = 0; i < G[cur].size(); i++){ //相邻未访问过的节点入队列
                if(!vis[G[cur][i]]){
                    vis[G[cur][i]] = true;
                    flag = false;
                    q.push(make_pair(G[cur][i], count));
                }
            }
            if(flag && count <= 2) //叶子节点且经过的的1不超过2
                res++;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，遍历每一个节点
空间复杂度： $O(n)$ ，辅助矩阵G的元素总共 $2n$ 个，辅助数组vis长度为 $n$ ，辅助队列长度最长为 $n$