8
6 8 7 4 5 1 3 2
8 5 4 7 6 3 2 1
输出样例:
R: 1 2 3 4 5
L: 1 6 7 8 5
思路
重建二叉树,然后深度优先遍历,如果是看右视图,就优先遍历右子树;如果是左视图,就优先遍历左子树。遍历过程中记录每个深度是否有节点已经被看到,打印出第一个被看到的节点。
代码#include
#include
using namespace std;
struct node {
int n;
node* l, *r;
node() {
l = r = NULL;
}
};
int last[25], mid[25];
node* build(int mb, int me, int lb, int le) {
if(mb > me || lb > le) return NULL;
node* t = new node();
t->n = last[le];
int m;
for(int i = mb; i <= me; ++i) {
if(mid[i] == last[le]) {
m = i;
break;
}
}
int ls = m-mb;
t->l = build(mb, m-1, lb, lb+ls-1);
t->r = build(m+1, me, lb+ls, le-1);
return t;
}
bool vis[20];
void right(node* tree, int depth) {
if(tree) {
if(!vis[depth]) {
printf(" %d", tree->n);
vis[depth] = true;
}
right(tree->r, depth+1);
right(tree->l, depth+1);
}
}
void left(node* tree, int depth) {
if(tree) {
if(!vis[depth]) {
printf(" %d", tree->n);
vis[depth] = true;
}
left(tree->l, depth+1);
left(tree->r, depth+1);
}
}
int main(void)
{
freopen("in.txt", "r", stdin);
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d", &mid[i]);
}
for(int i = 0; i < n; ++i) {
scanf("%d", &last[i]);
}
node* tree = build(0, n-1, 0, n-1);
memset(vis, 0, sizeof(vis));
printf("R:");
right(tree, 0);
printf("\n");
memset(vis, 0, sizeof(vis));
printf("L:");
left(tree, 0);
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)