PAT甲级-1102 Invert a Binary Tree

题目

 

题目大意

给定一个树的节点数n，每个节点的编号从0到n-1，并依次给出每个节点的孩子节点。要求输出这棵二叉树的翻转二叉树的层序遍历和中序遍历。

思路

求一棵二叉树的翻转树，在构建的时候将左右孩子换位即可。输入给出每个父节点（索引）所对应的孩子节点，所以可以用数组来存储树，二维数组也可以，结构体数组也行。

层序遍历的思路就是将根节点放入队列，然后将这个根节点对应的孩子节点入队，再将根节点出队，以出队后的首节点作为根节点，继续将它的孩子入队，接着出队，如此循环往复。可以先初始化队列，将根节点放入队列，然后将首节点的孩子节点入队和首节点出队这一过程作为循环的主体，循环的条件就是队列是否为空。

代码

#include <iostream>
#include <vector>
#include <cctype>
#include <queue>
using namespace std;struct node{int data;int lchild;int rchild;
};
int n;
vector<node> v;
vector<int> level;  // 层序遍历
vector<int> in;  // 中序遍历void traverseLevel(node root){queue<int> q;q.push(root.data);while (!q.empty()){if (root.lchild != -1){q.push(root.lchild);}if (root.rchild != -1){q.push(root.rchild);}level.push_back(q.front());q.pop();root = v[q.front()];  // 更新根节点}
}  // 层序遍历void traverseIn(node root){if (root.data != -1){if (root.lchild != -1){traverseIn(v[root.lchild]);}in.push_back(root.data);if (root.rchild != -1){traverseIn(v[root.rchild]);}}
}  // 中序遍历int main(){cin >> n;v.resize(n);vector<int> f(n, 0);  // 判断是否作为孩子节点for (int i = 0; i < n; i++){char c1, c2;cin >> c1 >> c2;v[i].data = i;if (isdigit(c1)){f[c1 - '0'] = 1;v[i].rchild = c1 - '0';}else{v[i].rchild = -1;  // 初始化为-1（因为有节点0），左右孩子取反}if (isdigit(c2)){f[c2 - '0'] = 1;v[i].lchild = c2 - '0';}else{v[i].lchild = -1;}}node root;for (int i = 0; i < n; i++){if (f[i] == 0){root = v[i];}}  // 找到根节点traverseLevel(root);traverseIn(root);for (int i = 0; i < n; i++){cout << level[i];if (i != n - 1){cout << " ";}}cout << endl;for (int i = 0; i < n; i++){cout << in[i];if (i != n - 1){cout << " ";}}cout << endl;return 0;
}