PAT A1102 Invert a Binary Tree 另外一种思路

题目链接

这道题《算法笔记》上面的代码中规中矩， 值得借鉴， 但其实考试的时候不需要写这么复杂， 甚至感觉， 算法笔记上面的思路有点奇葩， 不过作为思维训练的话， 还是很不错的。

长话短说 ，对这道题 ，我们完全没有必要把树翻转过来， 只需要在输出的时候反过来输出就行了。 比如说， 以前的中序遍历代码， 我们是按照

左孩子——根节点——右孩子 遍历，

现在改成

右孩子——根节点——左孩子 顺序即可.

代码如下：

//#2 2020.04.17 改变访问顺序就可以了 不需要真的改变结构
#include <cstdio>
#include <queue>
using namespace std;
struct Node{
	int lchild, rchild;
}node[20];
bool notRoot[20]={false};
int cnt=0;
void levelOrder(int root){
	queue<int> q;
	q.push(root);
	int cnt=0;
	while (!q.empty()){
		int now=q.front();
		q.pop();
		if (cnt++) printf(" ");
		printf("%d", now);
		if (node[now].rchild!=-1) q.push(node[now].rchild);
		if (node[now].lchild!=-1) q.push(node[now].lchild);
	}
}
void inOrder(int root){
	if (root==-1) return;
	inOrder(node[root].rchild);
	if (cnt++) printf(" ");
	printf("%d",root);
	inOrder(node[root].lchild);
}
int main(){
	int n;
	scanf("%d",&n);
	for (int i=0; i<n; i++){
		char c1,c2;
		getchar();//这个顺序真巧 
		scanf("%c %c", &c1, &c2);
		if (c1!='-'){
			node[i].lchild=c1-'0';
			notRoot[c1-'0']=true;
		}else {
			node[i].lchild=-1;
		}
		if (c2!='-'){
			node[i].rchild=c2-'0';
			notRoot[c2-'0']=true;
		}else {
			node[i].rchild=-1;
		}
	}
	int root;
	for (int i=0; i<n; i++){
		if (!notRoot[i]){
			root=i;
			break;
		}
	}
	levelOrder(root);
	printf("\n");
	inOrder(root);
}