1102 Invert a Binary Tree (25 分)

用静态二叉树，中序遍历和层序遍历都先右再左

// // Created by dgm on 2019/10/1. // #include <iostream> using namespace std; #define maxn 20 struct node{ int left; int right; }t[maxn]; int n; void inTraverse(int root,int &index){ if(root==-1)return ; inTraverse(t[root].right,index); if(index!=n-1)cout<<root<<" "; else cout<<root; index+=1; inTraverse(t[root].left,index); } void levelTraverse(int root){ int queue[maxn]; int front=0; int rear=0; int count=0; queue[rear++]=root; while(rear!=front){ int temp=queue[front++]; if(count!=n-1)cout<<temp<<" "; else cout<<temp; count++; if(t[temp].right!=-1) queue[rear++]=t[temp].right; if(t[temp].left!=-1) queue[rear++]=t[temp].left; } } int main(){ cin>>n; int findRoot[n]; int root; for (int i = 0; i < n; ++i) findRoot[i]=0; //用于标记没有被指向的节点，即根节点 for (int i = 0; i < n; ++i) { char child; cin>>child; t[i].left=(child=='-')?-1:child-'0'; if(child!='-')findRoot[child-'0']=1; cin>>child; t[i].right=(child=='-')?-1:child-'0'; if(child!='-')findRoot[child-'0']=1; } for (root = 0; root < n; ++root) { //寻找根节点 if(findRoot[root]!=1)break; } levelTraverse(root); cout<<endl; int index=0; inTraverse(root,index); return 0; }