=====|WUSTOJ 1651 根节点到指定结点的路径【二叉树】
题目来源于 http://acm.wust.edu.cn/problem.php?id=1651&soj=0
文章图片
★这题不是二叉树的应用，但要了解二叉树相关的知识qwq
相关知识： 二叉树的创建，我通过构造一个函数建立的，详见build函数。感谢我的同学的帮助，我是在太菜了awa
栈的先进后出的特性，这题我用得好别扭，但是我不会更好的办法了
思路： 首先根据输入字符串构建二叉树就不说了叭。通过栈来保存路径节点，然后从根节点开始一直往左找，左边找到返回1，没找到就找右边，右边也没找到就弹出栈顶元素。最后获得的栈一定是答案的路径，但别高兴的的太早 ，栈是先进后出的，不能直接输出。我就用了一个蹩脚的办法，大佬们见笑了。
注意： 【=====|WUSTOJ 1651 根节点到指定结点的路径【二叉树】】还是栈的特性，强调了三遍哦。重要的事情说三遍
代码：
#include
using namespace std;
string str;
char ss;
int now,len;
struct tree
{
tree * l;
tree * r;
char c;
};
stack s;
void build(tree * &T)
{
if(now>=len) return ;
if(str[now]=='^') {now++;
T=NULL;
}
else{
T=new tree();
T->c=str[now++];
build(T->l);
build(T->r);
}
}
bool hhh(tree * T)
{
if(T==NULL) return 0;
s.push(T);
if(T->c==ss) return 1;
bool b=0;
if(T->l!=NULL) b=hhh(T->l);
if(!b&&T->r!=NULL) b=hhh(T->r);
if(!b) s.pop();
return b;
}
int main()
{
while(cin>>str){
int n;
tree * T;
len=str.size();
now=0;
build(T);
cin>>n;
while(n--){
cin>>ss;
while(s.size()) s.pop();
if(hhh(T)){
char ch[105];
now=0;
while(s.size()){
ch[now++]=s.top()->c;
s.pop();
}
for(int i=now-1;
i>=0;
i--) cout< 推荐阅读
- WUSTOJ|WUSTOJ 1307: 校门外的树（Java）
- JavaScript刷题|[javascript]二叉树根节点到叶子节点和为指定值的路径
- 折返点1651|折返点1651 要不要成立个跑步俱乐部呢（）