A1102 Invert a Binary Tree (25分)(二叉树的中序遍历和层序遍历、静态二叉树的创建)

一、技术总结

1. 这一题主要学习到的有，二叉树的创建，可以使用静态链表的方，也就是创建一个只有记录左右子树下标的结构体，然后创建N个结点的结构体数组；
2. 同时对于这类题一般需要找出根结点，可以创建一个N个结点的数组，默认初始化为0，然后出现的结点下标都是左右子树，因此标记为1，然后从第一个结点开始遍历，第一个出现0的下标即为根结点下标；
3. 还有就是中序遍历和层序遍历的熟悉，层序遍历中一个注意点就是，进入while循环后，会从队列的首部弹出一个结点，记住后序操作都是以此结点为准，不然会出错；
4. 还有对于遍历输出技巧，可以遍历中使用一个vector向量接收遍历的顺序，最后在进行统一的输出；

二、参考代码

#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;
struct node{
	int id, l, r;
}a[100];
vector<int> vIn, vLe;
void levelOrder(int root){
	queue<int> q;
	q.push(root);
	while(!q.empty()){
		int top = q.front();
		vLe.push_back(top);
		q.pop();
		if(a[top].l != -1) q.push(a[top].l);
		if(a[top].r != -1) q.push(a[top].r);
	}
}
void inOrder(int root){
	if(root == -1){
		return;
	}
	inOrder(a[root].l);
	vIn.push_back(root);
	inOrder(a[root].r);
}
int main(){
	int n, root = 0, have[100] = {0};
	cin >> n;
	for(int i = 0; i < n; i++){
		string l, r;
		a[i].id = i;
		cin >> l >> r;
		if(l != "-"){
			a[i].r = stoi(l);
			have[stoi(l)] = 1;
		}else{
			a[i].r = -1;
		}
		if(r != "-"){
			a[i].l = stoi(r);
			have[stoi(r)] = 1;
		}else{
			a[i].l = -1;
		}
	}
	while(have[root] == 1) root++;
	levelOrder(root);
	inOrder(root);
	for(int i = 0; i < n; i++){
		if(i != 0) printf(" ");
		printf("%d", vLe[i]);
	}
	cout << endl;
	for(int i = 0; i < n; i++){
		if(i != 0) printf(" ");
		printf("%d", vIn[i]);
	}
	return 0;
}