目录
1，题目描述
题目描述
2，思路
3，AC代码
4，解题过程
1，题目描述
- Homebrew：自制的，家酿的；
- invert：颠倒的事物；倒置物；倒悬；
Sample Input:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6 Sample Output:
3 7 2 6 4 0 5 1
6 5 7 4 3 2 0 1 题目描述
输出树的镜像中序遍历和镜像层次遍历。
2，思路
1，构建树
2，寻找树的根节点：
3，镜像层次遍历：
4，镜像中序遍历
3，AC代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int left, right;
}tree[11];
vector<int> in, level;
int N;
void inOrder(int root){ //获得镜像中序遍历序
if(root == -1) return;
inOrder(tree[root].right); //先右后左
in.push_back(root);
inOrder(tree[root].left);
}
void levelOrder(int root){ //获得镜像层次遍历序
queue<int> q;
q.push(root);
while(!q.empty()){
int p = q.front();
level.push_back(p);
q.pop();
if(tree[p].right != -1) q.push(tree[p].right); //先右后左
if(tree[p].left != -1) q.push(tree[p].left);
}
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGE
scanf("%d\n", &N); // !!!注意\n
char left, right;
int root;
bool isRoot[11];
fill(isRoot, isRoot + N, true);
for(int i = 0; i < N; i++){
scanf("%c %c\n", &left, &right); // !!!注意\n
tree[i].left = left == '-' ? -1 : (left - '0');
tree[i].right = right == '-' ? -1 : (right - '0');
if(tree[i].left != -1) isRoot[tree[i].left] = false;
if(tree[i].right != -1) isRoot[tree[i].right] = false;
}
for(int i = 0; i < N; i++) //寻找根节点
if(isRoot[i]) root = i;
inOrder(root);
levelOrder(root);
printf("%d", level[0]);
for(int i = 1; i < N; i++)
printf(" %d", level[i]);
printf("\n%d", in[0]);
for(int i = 1; i < N; i++)
printf(" %d", in[i]);
return 0;
}