题解 | #路径数目#
路径数目
http://www.nowcoder.com/practice/e503e7c18e2c440991f60ce5d35f19d7
题意：
给你一棵
个节点的有根树，根节点为1，每个节点的权值为0或者1，问有多少条从根节点到叶子节点的路径，使得所经过的节点权值和不超过2 ？
解法一（深度优先搜索）
从根节点对整棵树进行dfs，然后计算答案
具体的：
我们定义递归函数)
表示当前是以点
为根节点的子树，并且点的父亲节点为
，当前经过的节点权值和为
，节点权值数组为
1. 将当前的变量加上对应节点的权值，即
2. 若大于2，则往下走到叶子结点一定不合法，故直接返回
3. 枚举当前节点的所有儿子节点
（注意判断是否是父亲节点），然后往下递归，即)
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;
}
}; 时间复杂度：空间复杂度：
解法二（广度优先搜索）
我们可以按照解法一按照层次遍历的顺序来计算答案
代码：
/**
* 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;
}
}; 时间复杂度： 空间复杂度：)
，邻接表存图，
数组都是大小的，故总的空间复杂度为
