【PAT甲级】1102 Invert a Binary Tree（反转二叉树）

二叉树构建好以后，中序遍历模拟一次，模拟时先走右子树再走左子树，即可得到反转后的中序遍历。再走一次BFS，BFS时同样先走右子树再走左子树，就是反转后的层序遍历。
PS：也可以在构造二叉树时直接输入反转后的二叉树（先输入右子树再输入左子树），后面的DFS和BFS就不需要更改左右次序了。

#include using namespace std;const int N = 20;
int n;
int l[N], r[N];
int in[N], level[N];
bool hf[N];void dfs(int u, int &k)
{if(r[u] != -1) dfs(r[u], k);in[k++] = u;if(l[u] != -1) dfs(l[u], k);
}void bfs(int u)
{int idx = 0;queue<int> q;q.push(u);while(q.size()){auto t = q.front();q.pop();level[idx++] = t;if(r[t] != -1) q.push(r[t]);if(l[t] != -1) q.push(l[t]);}
}int main()
{cin >> n;for(int i = 0; i < n; i ++){char a, b;cin >> a >> b;if(a != '-'){l[i] = a - '0';hf[a - '0'] = true;}else l[i] = -1;if(b != '-'){r[i] = b - '0';hf[b - '0'] = true;}else r[i] = -1;}int root = 0;while(hf[root]) root ++;int k = 0;dfs(root, k);bfs(root);cout << level[0];for(int i = 1; i < n; i ++) cout << ' ' << level[i];cout << endl;cout << in[0];for(int i = 1; i < n; i ++) cout << ' ' << in[i];cout << endl;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！