本文主要是介绍uva 112，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：求构造的树，是否有一条路和为给定值。。#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;struct tree
{int value;struct tree *lchild;struct tree *rchild;
};
tree *root;
bool found;
int I;int tonum(char *s)
{int len = strlen(s);int re = 0 ;int i = 0 ;if (s[0] == '-')i++;for ( ; i < len ; i++)re = re*10 + s[i] - '0';if (s[0] == '-')re = -re;return re = 0 ? -999999:re ; //0是不可取的
}void build(tree *&ch) //引用根节点，不失为一种处理树的根节点的好方法
{char c;char str[100];int count = 0;bool isnum = false ;while (cin>>c){if ((c>='0'&c<='9') | c == '-'){isnum = true;str[count++] = c ;str[count] = '\0'; // notice }else if ( !isnum && c == ')') // 叶节点标记是(){ch = NULL ;return ;}else if (isnum && !(c>='0'&&c<='9')){if (tonum(str) == -999999)return ;ch = new tree;ch->value = tonum(str);char c11;build(ch->lchild);build(ch->rchild);while (cin>>c11){if (c11 == ')')return ;}return ;}}
}void dfs(tree *a,int n)
{if (found) // 深搜的结果是最后的解return ;if (!a->lchild && !a->rchild){if (n+a->value == I)found = true;return ;}if (a->lchild) dfs(a->lchild,n+a->value);if (a->rchild) dfs(a->rchild,n+a->value);
}int main()
{while ( cin>>I ){getchar();root = NULL ;build(root);if (!root){cout<<"no"<<endl;continue;}found = false ;dfs(root,0);if (found)cout<<"yes"<<endl;else cout<<"no"<<endl;}return 0;
}大神的递归做法：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int flag ;
int t_sun(int n,int sum)
{int data;char c;cin>>c; //左括号 cin>>data;if(!(cin == 0)){sum +=data;int ok1 = t_sum(n,sum);int ok2 = t_sum(n,sum);if(!ok1 && !ok2 && !flag)if(sum == n)flag = 1;cin>>c ; //右括号return 1;}else {cin.clear();cin>>c ; // notice return 0 ;}
}
int main()
{int n;while(cin>>n){flag = 0 ;t_sum(n,0);cout<<(flag?"yes":"no")<<endl;}return 0 ;
}这篇关于uva 112的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
