题解 | #路径数目#

路径数目

http://www.nowcoder.com/practice/e503e7c18e2c440991f60ce5d35f19d7

题意：

给你一棵 $n$ 个节点的有根树，根节点为1，每个节点的权值为0或者1，问有多少条从根节点到叶子节点的路径，使得所经过的节点权值和不超过2 ？

解法一（深度优先搜索）

从根节点对整棵树进行dfs，然后计算答案

具体的：

我们定义递归函数 $dfs(u,fa,cnt,f)$ 表示当前是以点 $u$ 为根节点的子树，并且点 $u$ 的父亲节点为 $fa$ ，当前经过的节点权值和为 $cnt$ ，节点权值数组为 $f$

1. 将当前的 $cnt$ 变量加上对应节点的权值，即 $cnt+=f[u-1]$

2. 若 $cnt$ 大于2，则往下走到叶子结点一定不合法，故直接返回

3. 枚举当前节点 $u$ 的所有儿子节点 $v$ （注意判断是否是父亲节点），然后往下递归，即 $dfs(v,u,cnt,f)$

4. 若当前节点没有儿子节点，则直接将答案+1

代码：

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */

class Solution {
public:
    int ans;//答案
    vector<int> gr[100001];//邻接表存图
    void dfs(int u,int fa,int cnt,vector<int>& f){
        cnt+=f[u-1];//累加权值和
        if(cnt>2)return;//若大于2，直接返回
        bool flag=true;//标记当前节点是否有儿子节点
        for(auto v:gr[u]){
            if(v==fa)continue;
            flag=false;
            dfs(v,u,cnt,f);
        }
        if(flag)ans++;//当前节点是叶子节点
    }
    int solve(int n, vector<Point>& Edge, vector<int>& f) {
        ans=0;
        for(int i=1;i<=n;i++){
            gr[i].clear();//多测清空
        }
        for(auto e:Edge){
            //建双向边
            gr[e.x].push_back(e.y);
            gr[e.y].push_back(e.x);
        }
        dfs(1,0,0,f);
        return ans;
    }
};

时间复杂度： $O(n)$ ，我们只需要对整棵树进行一次dfs，故总的时间复杂度为 $O(n)$
空间复杂度： $O(n)$ ，邻接表存图， $f,Edge$ 数组都是 $O(n)$ 大小的，故总的空间复杂度为 $O(n)$

解法二（广度优先搜索）

我们可以按照解法一按照层次遍历的顺序来计算答案

代码：

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */

class Solution {
public:
    vector<int> gr[100001];//邻接表存图
    int father[100001];//父节点数组
    struct node{//队列元素结构体
        int p,cnt;//p为当前节点，cnt为当前节点权值和
        inline node(int p,int cnt):p(p),cnt(cnt){}
    };
    int solve(int n, vector<Point>& Edge, vector<int>& f) {
        for(int i=1;i<=n;i++){
            gr[i].clear();//多测清空
        }
        for(auto e:Edge){
            //连双向边
            gr[e.x].push_back(e.y);
            gr[e.y].push_back(e.x);
        }
        memset(father,0,sizeof father);//多测清空
        queue<node> que;
        que.push(node(1,f[0]));
        int ans=0;
        while(!que.empty()){
            node t=que.front();//弹出队头
            que.pop();
            int u=t.p,cnt=t.cnt;
            bool flag=true;//标记是否有儿子节点
            for(auto v:gr[u]){
                if(v==father[u])continue;
                father[v]=u;//标记u的儿子节点的父亲节点为u
                flag=false;
                if(cnt+f[v-1]<=2){
                    que.push(node(v,cnt+f[v-1]));//塞入队列
                }
            }
            if(flag)ans++;//是叶子节点，计算答案
        }
        return ans;
    }
};

时间复杂度： $O(n)$ ，我们只需要对整棵树进行一次bfs，故总的时间复杂度为 $O(n)$

空间复杂度： $O(n)$ ，邻接表存图， $f,Edge$ 数组都是 $O(n)$ 大小的，故总的空间复杂度为 $O(n)$