PAT 甲级 1102 Invert a Binary Tree (25 分)

思路：

1.在构造二叉树时将左右结点互换；
2.中序遍历二叉树，遍历时将遍历序列用数组存储起来，就是中序序列；
3.每遍历到一个结点，将这个结点放入它所在层次的序列后面，因为我们在中序遍历时可以保证同一层次，左边的结点一定会在右边的结点之前遍历到；

代码：

#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;
vector<pair<int,int>> v;
map<int,vector<int>> mp;
vector<int> in;
void inOrder(int root,int level){
	mp[level].push_back(root);
	if(v[root].first!=-1) inOrder(v[root].first,level+1);
	in.push_back(root);
	if(v[root].second!=-1) inOrder(v[root].second,level+1);
}
int main(){
	int n;
	cin>>n;
	v.resize(n);
	int root=n*(n-1)/2;
	for(int i=0;i<n;i++){
		string s[2];
		cin>>s[0]>>s[1];
		for(int j=0;j<2;j++)
			if(s[j]!="-"){
				int a=stoi(s[j]);
				j==0?v[i].second=a:v[i].first=a;
				root-=a;
			}else j==0?v[i].second=-1:v[i].first=-1;
	}
	inOrder(root,1);
	printf("%d",root);
	for(auto i:mp)
		for(auto j:i.second) printf(j==root?"":" %d",j);
	printf("
%d",in[0]);
	for(int i=1;i<n;i++) printf(" %d",in[i]);
	return 0;
}