tree,
这是一个编程题模板。
已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：
所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。
输入格式:
输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。
输出格式:
输出可能的中序遍历序列的总数，结果不超过长整型数。
输入样例:
在这里给出一组输入。例如：
abc
cba
输出样例:
在这里给出相应的输出。例如：
4#include <bits/stdc++.h>
using namespace std;
string a, b;
int dfs(int l1,int r1,int l2,int r2)
{
if(l1 > r1) return 1;
if(a[l1] != b[r2]) return 0;
int cnt = 0;
for(int i = l1; i <= r1; i++)
{
int lcnt = dfs(l1 + 1, i, l2, i - l1 - 1 + l2);
int rcnt = dfs(i + 1, r1, i - l1 + l2, r2 - 1);
if(lcnt && rcnt)
{
cnt += lcnt * rcnt;
}
}
return cnt;
}
int main()
{
cin >> a >> b;
cout << dfs(0, a.size() - 1, 0, b.size() - 1);
}先序序列创建二叉树，输出先序序列、中序序列、后序序列并输出叶子结点数
分数 10
全屏浏览
切换布局
作者 夏仁强
单位 贵州工程应用技术学院
对于给定的二叉树，输出其先序序列、中序序列、后序序列并输出叶子结点数。
输入格式:
二叉树的先序遍历序列。
提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。
输出格式:
若是非空二叉树，则输出四行内容 第一行是二叉树的先序遍历序列； 第二行是二叉树的中序遍历序列； 第三行是二叉树的后序遍历序列； 第四行是叶子结点数；
若是空二叉树 只需输出叶子数0
输入样例1:
FCA##DB###EHM###G##
输出样例1:
FCADBEHMG
ACBDFMHEG
ABDCMHGEF
4
输入样例2:
#
输出样例2:
0
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
#include <bits/stdc++.h>
using namespace std;
unordered_map<char, char> l, r;
unordered_map <char, int>pos;
string pre, in, post;
string s;
int flag ;
int cnt, res;
int build(int pl, int pr, int il, int ir)
{
if(il > ir)
{
flag = 1;
return 0 ;
}
else
{
char root = pre[pl];
int k = pos[root];
if(il < k) l[root] = build(pl + 1, pl + k - il, il,k -1);
if(ir > k) r[root] = build(pl + k - il +1, pr, k + 1, ir);
return root;
}
}
void dfs(char u)
{
if(l[u]) dfs(l[u]);
if(r[u]) dfs(r[u]);
post += u;
}
void ye(int u)
{
if(!l[u] && !r[u]) res++;
if(l[u]) ye(l[u]);
if(r[u]) ye(r[u]);
}
int main()
{
cin >> s;
if(s == "#")
{
cout << 0;
return 0;
}
stack<char> stk;
for(int i = 0; i < s.size(); i++)
{
if(s[i] != '#')
{
pre += s[i];
stk.push(s[i]);
}
else
{
if(!stk.empty())
{
in += stk.top();
stk.pop();
}
}
}
for(int i = 0; i < pre.size(); i++)
{
pos[in[i]] = i;
}
build(0, pre.size() - 1, 0, in.size() -1);
char root = pre[0];
dfs(root);
ye(root);
if(flag) cout << res;
else
{
cout << pre << endl << in << endl << post << endl << res;
// cout << post << endl;
}
}二叉树的遍历
分数 10
全屏浏览
切换布局
作者 chchye
单位 广东东软学院
根据输入构造二叉树，输出该二叉树的先序序列。二叉树共有N个节点，节点编号是1到N。约定1号节点是根节点。
输入格式:
第一行输入整数N。
接下来有N行，依次给出1到N节点的左孩子和右孩子。对于这N行中的每一行，有两个整数。第i（i=1, 2, ..., N）行中，第一个整数指出左孩子的编号，第二个整数指出右孩子的编号。如果整数值为0，表示没有左孩子或右孩子。
输出格式:
输出一行，内容是二叉树的先序序列。节点编号之间用空格隔开，行末有1个空格。
输入样例:
6
2 5
3 4
0 0
0 0
0 6
0 0
输出样例:
1 2 3 4 5 6
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int l[N], r[N];
int res[N], cnt;
bool fa[N];
void dfs(int u)
{
if(u == 0) return ;
res[cnt++] = u;
if(l[u]) dfs(l[u]);
if(r[u]) dfs(r[u]);
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
if(a)
{
l[i] = a;
fa[a] = true;
}
if(b)
{
r[i] = b;
fa[b] = true;
}
}
int root = 1;
while(fa[root]) root++;
dfs(root);
// cout << 1;
for(int i = 0; i < n; i++) cout << res[i]<< " ";
}求后序遍历
分数 10
全屏浏览
切换布局
作者 刘昆
单位 中国矿业大学徐海学院
Background
Special for beginners, ^_^
Description
输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。
Format
Input
输入共两行。
第一行一个字符串，表示树的先序遍历；
第二行一个字符串，表示树的中序遍历。
树的结点一律用小写字母表示，长度小于 50。
Output
输出仅一行，表示树的后序遍历序列。
Samples
样例输入
abdec
dbeac
样例输出
debca
Limitation
1s, 1024KiB for each test case.
#include <bits/stdc++.h>
using namespace std;
string s1, s2;
unordered_map <char, char>l, r;
unordered_map<char, int>pos;
char build(int pl, int pr, int il, int ir)
{
// if(il > ir) return 0;
char root = s1[pl];
int k = pos[root];
if(k > il) l[root] = build(pl + 1,pl - il + k,il, k - 1);
if(k < ir) r[root] = build(pl - il + k + 1, pr, k + 1, ir);
return root;
}
void dfs(char u)
{
if(l[u]) dfs(l[u]);
if(r[u]) dfs(r[u]);
cout << u;
}
int main()
{
cin >> s1 >> s2;
for(int i = 0; i < s2.size(); i++)
{
pos[s2[i]] = i;
}
char root = build(0, s1.size() - 1, 0, s2.size() - 1 );
dfs(root);
}二叉树遍历
分数 10
全屏浏览
切换布局
作者 刘昆
单位 中国矿业大学徐海学院
Background
Special for beginners, ^_^
Description
树和二叉树基本上都有先序、中序、后序、层序遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。
假定一棵二叉树一个结点用一个字符描述，现在给出中序和层序遍历的字符串，求该树的先序遍历字符串。
Format
Input
输入共两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和层序遍历的序列。字符串长度小于50。
Output
输出就一行，表示二叉树的先序序列。
Samples
样例输入
DBEAC
ABCDE
样例输出
ABDEC
Hint
提示：在层序遍历中，子树中的根节点一定编号最小。
Limitation
1s, 1024KiB for each test case.
#include <bits/stdc++.h>
using namespace std;
string a, b;
const int N = 35;
unordered_map<int, int>l, r;
unordered_map<char, int>pos;
bool st[N];
int idx;
void dfs(int root)
{
cout << b[root];
if(l[root]) dfs(l[root]);
if(r[root]) dfs(r[root]);
}
int main()
{
cin >> a >> b;
for(int i = 0; i < a.size(); i++) pos[a[i]] = i;
queue<int>q;
int root = 0;
q.push(root);
while(!q.empty())
{
int t = q.front();
q.pop();
int k =pos[b[t]] ;
st[k] = true;
if(k > 0 && !st[k - 1] )
{
l[t] = ++idx;
q.push(idx);
}
if(k < b.size() -1 && !st[k + 1] )
{
r[t] = ++idx;
q.push(idx);
}
}
// cout << l[root] << r[root] << endl;
dfs(root);
}完全二叉树的权值
分数 20
全屏浏览
切换布局
作者 y
单位 成都锦城学院
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序为A1,A2,A3⋅⋅⋅AN
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
输入格式:
第一行包含一个整数N（1 ≤ N ≤ 100000）
第二行包含 N个整数，A1,A2,A3⋅⋅⋅AN（-100000 ≤ Ai ≤ 100000）
输出格式:
输出一个整数代表答案，结尾无空格换行。
输入样例:
在这里给出一组输入。例如：
7
1 6 5 4 3 2 1
输出样例:
在这里给出相应的输出。例如：
2
题目来源：蓝桥杯省赛真题
层次遍历
分数 10
全屏浏览
切换布局
作者 usx程序设计类课程组
单位 绍兴文理学院
给定二叉树的包含虚结点的先序遍历序列信息，按层次顺序给出遍历的结果。
输入格式:
首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据在一行中输入一个字符串（不含空格且长度不超过80），表示二叉树的先序遍历序列（其中@表示虚结点）。
输出格式:
对于每组测试，输出层次遍历的结果。
输入样例:
1
ABD@@EG@@@C@F@@
输出样例:
ABCDEFG#include <bits/stdc++.h>
using namespace std;
unordered_map<char, char>l, r;
int idx;
string s;
char dfs(char u)
{
// if(u == '@') return 0;
if(u != '@' ) l[u] = dfs(s[++idx]);
if(u != '@' ) r[u] = dfs(s[++idx]);
return u;
}
int main()
{
int t;
cin >> t;
while(t--)
{
l.clear();
r.clear();
idx = 0;
cin >> s;
dfs(s[0]);
queue<char> q;
q.push(s[0]);
// cout << l['E'] << endl;
while(!q.empty())
{
char t = q.front();
if(t != '@') cout << t;
q.pop();
if(l[t]) q.push(l[t]);
if(r[t]) q.push(r[t]);
}
cout << endl;
}
}原文地址：https://blog.csdn.net/black_blank/article/details/144123208
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！