【LSP】c_pat_由后序遍历和中序遍历确定层序遍历（利用性质
http://cdn.u1.huluxia.com/g4/M01/5B/44/rBAAdl9u_uWAe5mOAACt4WdlvYs156.jpg
现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。
思路
#include<bits/stdc++.h>
using namespace std;
const int N=35;
int n, post, in;
unordered_map<int, int> mp;
struct node {
int val;
node *left, *right;
};
node* dfs(int inL, int inR, int postL, int postR) {
if (postL>postR) return NULL;
int k=mp], lsz=k-inL;
node* root=new node();
root->val=post;
root->left=dfs(inL, k-1, postL, postL+lsz-1);
root->right=dfs(k+1, inR, postL+lsz, postR-1);
return root;
}
void bfs(node* root) {
queue<node*> q; q.push(root);
int c=0;
while (!q.empty()) {
for (int i=q.size(); i>0; i--) {
auto now=q.front(); q.pop();
cout<<now->val;
if (c++!=n-1) cout<<' ';
if (now->left!=NULL)q.push(now->left);
if (now->right!=NULL) q.push(now->right);
}
}
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
for (int i=0; i<n; i++) cin>>post;
for (int i=0; i<n; i++) cin>>in, mp]=i;;
bfs(dfs(0, n-1, 0, n-1));
return 0;
}http://cdn.u1.huluxia.com/g4/M01/5B/44/rBAAdl9u_uWAED0QAAEcL_BTB1k107.jpg
页:
[1]