PAT A1020 Tree Traversals (25分)

前言

传送门

正文

参考题解

#include <bits/stdc++.h> using namespace std; /* 题意：二叉树后序和中序遍历，求层次遍历 */ const int N=50; //树节点 struct Node{ int data; Node* lchild; Node* rchild; }; int pre[N],post[N],in[N];//前序，中序，后序遍历 //根据后序和中序建树 Node* create(int postL,int postR,int inL,int inR){ if(postL>postR)return NULL;//递归边界 Node *root = new Node;//根节点 root->data = post[postR]; int k; for (k = inL; k <=inR ; ++k) { if (in[k] == post[postR]) { break;//找到根节点在中序遍历中的位置 } } int cntL = k - inL;//左子树结点个数 root->lchild = create(postL, postL + cntL - 1, inL, k - 1); root->rchild = create(postL + cntL, postR - 1, k + 1, inR); return root; } int num=0;//已输出的结点个数 //层次遍历（注意参数是Node*） void bfs(Node* root){ queue<Node*> q; q.push(root); while (!q.empty()) { Node* now = q.front(); if(num!=0)printf(" "); printf("%d", now->data); num++; q.pop(); if (now->lchild!=NULL)q.push(now->lchild); if (now->rchild!=NULL)q.push(now->rchild); } } int main(){ int n; cin>>n; for (int i = 0; i < n; ++i) { cin >> post[i]; } for (int i = 0; i < n; ++i) { cin >> in[i]; } Node *root = create(0, n - 1, 0, n - 1); bfs(root); return 0; }