UVa 11234 Expressions (二叉树重建&由叶往根的层次遍历)

画图出来后结果很明显

2
xyPzwIM
abcABdefgCDEF sample output
wzyxIPM
gfCecbDdAaEBF *
+ -
x y z w F
B E
a A d D
b c e C
f g
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std; struct node
{
node(node* l, node* r, char ch): left(l), right(r), c(ch) {}
node* left;
node* right;
char c;
}*root; void build_tree(string & str)
{
stack<node*> st;
for(int i=0;i<str.length();i++)
{
if(islower(str[i]))
{
st.push(new node(0, 0, str[i]));
}
else
{
node* right=st.top(); st.pop();
node* left=st.top(); st.pop();
st.push(new node(left, right, str[i]));
}
} root=st.top();
} vector<char> ans; void bfs()
{
ans.clear();
queue<node*> q;
q.push(root);
while(!q.empty())
{
node* nd=q.front();q.pop();
ans.push_back(nd->c);
if(nd->left)
{
q.push(nd->left);
} if(nd->right)
{
q.push(nd->right);
}
}
} void delete_tree(node* nd)
{
if(nd)
{
delete_tree(nd->left);
delete_tree(nd->right);
delete nd;
}
} void output()
{
for(int i=ans.size()-1;i>=0;i--)
cout<<ans[i];
cout<<endl;
} int main()
{
int n;
cin>>n;
string str;
while(n--)
{
cin>>str;
build_tree(str);
bfs();
delete_tree(root);
output();
} return 0;
}
上一篇:监听浏览器种类,并区分safari和chrom浏览器


下一篇:应该具备的调试技能(java)