题目

题目描述``` 输入一串二叉树，以及它的先序遍历，判断该先序遍历是否正确，若正确则输出 Right，若不正确，则输出正确的先序遍历。

输入格式 第一行为二叉树的结点数 ( 1 ≤ 100 ) n(1≤n≤100)。

之后 n 行，每行包含 3 3 个整数，分别为当前结点序号，以及其左右儿子序号，用空格隔开。（ -1 表示空结点）

保证：

这 n 个结点的编号为 1 ∼ 1∼n 。

第一行为根结点的信息。

最后一行：一行 n 个整数，为给定的先序遍历，空格隔开。

输出格式 输出一行，Right 或正确的先序遍历的序列（ 1 1 个空格隔开）。

样例 #1 样例输入 #1

5
3 1 2
1 5 4
2 -1 -1
5 -1 -1
4 -1 -1
5 1 4 3 2

样例输出 #1``` 3 1 5 4 2 样例输入 #2

5
3 1 2
1 5 4
2 -1 -1
5 -1 -1
4 -1 -1
3 1 5 4 2
样例输出 #2

Right

代码

#include <bits/stdc++.h>

using namespace std;

struct node{
	int left;
	int right;
	int data;
	int father;
}Tree[1000000];
int a[10000];

void XianXu(int root,int cmp){
    if (Tree[root].left==-1&&Tree[root].right==-1){
   		a[cmp] = root;
   		return;
    }
	a[cmp] = root;
	if (Tree[root].left!=-1) XianXu(Tree[root].left,cmp+1);
	if (Tree[root].right!=-1) XianXu(Tree[root].right,cmp+1);
}

int main()
{
	int n,id;
	cin >> n;
	 // memset(Tree,-1,sizeof(Tree));
	for (int i=1;i<=n;++i){
		cin >> id;
		int l,r;
		cin >> l >> r;
		Tree[id].data = id;
		Tree[id].left = l;
		Tree[id].right = r;
	}
	XianXu(1,1);
	bool flag=1;
	for (int i=1;i<=n;++i){
		int x;
		cin >> x;
		if (x != a[i]) flag=0;
	}
	if (flag) cout << "Right" << endl;
	else{
		for(int i=1;i<=n;++i){
			cout << a[i] << ' ';
		}
	}
    return 0;
}