文章图片
文章图片
题意： 二叉树有N个节点（节点编号为0 ~ N-1），给出每个节点的左右孩子节点的编号，把该二叉树反转（即把每个节点的左右子树都交换），输出反转后二叉树的层序遍历序列和中序遍历序列。
思路： 【PAT|PAT甲级 1102 Invert a Binary Tree 反转树再层序中序输出】我们可以在读入数据的时候就直接把左右子树互换，然后再层序和中序遍历即可。
代码如下：
#include
#include
#include
using namespace std;
struct tree{
int key;
int left;
int right;
tree(){
left=right=-1;
}
};
vector t;
int n;
int level[100],in[100];
int ans=0;
int flag[100]={0};
void level_traversal(int root){//层序遍历
queue q;
q.push(t[root]);
while(!q.empty()){
tree temp=q.front();
level[ans++]=temp.key;
if(temp.left>=0){
q.push(t[temp.left]);
}
if(temp.right>=0){
q.push(t[temp.right]);
}
q.pop();
}
}void in_order(int root){//中序遍历
if(t[root].left>=0){
in_order(t[root].left);
}
in[ans++]=t[root].key;
if(t[root].right>=0){
in_order(t[root].right);
}
}int main(){
cin>>n;
t.resize(n);
char l,r;
for(int i=0;
i>l>>r;
if(l!='-'){
flag[l-'0']=1;
t[i].right=l-'0';
}
if(r!='-'){
flag[r-'0']=1;
t[i].left=r-'0';
}
t[i].key=i;
}int root;
for(int i=0;
i 推荐阅读
- PAT|Heaps
- PAT|(pat)A1030. Travel Plan
- PAT|DevC++使用技巧
- 码力提高题|UOJ#57./bzoj3051 【WC2013】(平面图转对偶图)
- PTA|PAT 1012Invert a Binary Tree反转二叉树（反转树，层序，中序）
- #|数据结构之树的存储结构
- #|数据结构之二叉树深度计算
- PAT|1061 判断题 （15 分）