PAT_甲级_1053 Path of Equal Weight

题目大意:

给定一颗树和每个结点的权值,求从所有根结点到叶子结点的路径,使得每条路径上的权值之和等于给定的常数S.如果有多条路径,按照路径的非递增序列输出

算法思路:

考察树的遍历,由于需要求从所有根结点到叶子结点的路径,很自然就想到使用先序遍历该树,并且使用$path$保存当前搜索路径,$result$保存所有符合条件的路径,如果当前结点是叶子结点,那么就先将此结点添加到$path$中,然后再计算$path$总所有结点的总权重,如果和给定的S相等,那么就将$path$添加进$result$中。接着得回退,先将叶子结点退出$path$,然后再返回。如果当期结点不是叶子结点,那么就先将当前结点添加进$path$中,然后再递归遍历其每一个孩子结点,在每一个孩子都遍历完毕后就将当期结点退出$path$,这样就完成了整个树的搜索过程。搜索结束后,$result$就保存了所有满足条件的路径,接着就是将$result$的每一条路径序列按照字典序从大到小排序,最后再输出即可。

注意点:

  • 1、在不排序的情况下,可以获得10分,测试点0和2错误。
  • 2、测试点2的错误和测试点5的段错误均是因为排序函数的问题,首先得注意是对权值排序,不是结点的ID(这个很容易搞错),然后就是对于两个序列的正反比较逻辑都得写,也就是对于同一个位置i,a[i]>b[i]和a[i]

提交结果:

图片.png

AC代码:

#include
#include
#include

using namespace std;

struct Node{
    int weight;
    vector child;
}node[110];

vector path;//当前搜索路径
vector > result;//所有满足条件的解

bool cmp(vector a,vector b){
    int len = min(a.size(),b.size());
    for(int i=0;inode[b[i]].weight){
            return true;
        }else if(node[a[i]].weightb.size();// 不写这个出现段错误 
}

void preTraverse(int root,int weight){
    if(node[root].child.empty()){
        // 叶子结点
        path.push_back(root);
        // 计算当前路径的权值
        int sum = 0;
        for(int i=0;i

你可能感兴趣的