PAT 1012Invert a Binary Tree 반전 두 갈래 트리(반전 트리, 레이어 순서, 중간 순서)

1497 단어 PTA나무.
전송
제목은 두 갈래 트리를 지정합니다. 반전 후 두 갈래 트리의 층차 역행 서열과 중차 역행 서열을 출력해야 합니다.
반전 조작에 관해서는 후순이나 선순이 모두 가능하다
#include
#define rep(i,a,n) for(int i=a;inode[N];
vectorans,res;
void gao(int root){
    if(root==-1) return ;
    gao(node[root].x);
    gao(node[root].y);
    swap(node[root].x,node[root].y);
}
void bfs(int root){
    queueq;
    q.push(root);
    while(!q.empty()){
        int p=q.front();
        q.pop();
        ans.push_back(p);
        if(node[p].x!=-1) q.push(node[p].x);
        if(node[p].y!=-1) q.push(node[p].y);
    }
    rep(i,0,ans.size())
        printf("%d%c",ans[i],i==ans.size()-1?'
':' '); } void dfs(int root){ if(node[root].x!=-1)dfs(node[root].x); res.push_back(root); if(node[root].y!=-1)dfs(node[root].y); return ; } int vis[N]; int main(){ cin>>n; rep(i,0,n) { char a,b; cin>>a>>b; if(a!='-') node[i].x=a-'0',vis[a-'0']=1; else node[i].x=-1; if(b!='-') node[i].y=b-'0',vis[b-'0']=1; else node[i].y=-1; } int root=0; while(vis[root]) root++; gao(root); bfs(root); dfs(root); rep(i,0,res.size()) printf("%d%c",res[i],i==res.size()-1?'
':' '); return 0; }

좋은 웹페이지 즐겨찾기