PAT A1102 Invert a Binary Tree
非常善良的题目，输入时交换所有的left和right，然后层序和中序输出即可
#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
struct Node{
int left;
int right;
};
vector<Node> vn;
int shot[10] = {0};
queue<int> q;
void bfs(int root){
q.push(root);
while(!q.empty()){
int idx = q.front();
q.pop();
cout << idx;
if(vn[idx].left != -1) q.push(vn[idx].left);
if(vn[idx].right != -1) q.push(vn[idx].right);
if(!q.empty()) cout << ' ';
}
cout << endl;
}
int cnt = 0,num;
void inOrder(int root){
if(vn[root].left != -1) inOrder(vn[root].left);
cout << root;
cnt ++;
if(cnt != num) cout << ' ';
else cout << endl;
if(vn[root].right != -1) inOrder(vn[root].right);
}
int main(){
cin >> num;
vn.resize(num);
for(int i = 0;i < num;i ++){
string l,r;
cin >> l >> r;
r == "-" ? vn[i].left = -1 : vn[i].left = stoi(r);
l == "-" ? vn[i].right = -1 : vn[i].right = stoi(l);
shot[vn[i].left] = shot[vn[i].right] = 1;
}
int root;
for(int i = 0;i < num;i ++){
if(shot[i] == 0){
root = i;
break;
}
}
bfs(root);
inOrder(root);
return 0;
}
Processed:
0.008, SQL:
9
