已知层序和中序也可以唯一确定一棵树,构建树的思路是遍历层序在中序中寻找优先输出根结点的位置,并递归建树,每次递归层序的范围不改变。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int level[maxn],in[maxn];struct node{int key;node *left,*right;
};node *build(int l,int r,int ll,int rr){if(l>r)return nullptr;int i,j;for(i=ll;i<=rr;i++){bool flag=true;for(j=l;j<=r;j++){if(level[i]==in[j]){flag=false;break;}}if(!flag) break;}node *root=new node();root->key=level[i];root->left=build(l,j-1,ll,rr);root->right=build(j+1,r,ll,rr);return root;}void preorder(node *root){if(root==nullptr)return;printf("%d ",root->key);preorder(root->left);preorder(root->right);
}int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&in[i]);}for(int i=0;i<n;i++){scanf("%d",&level[i]);}node *root=build(0,n-1,0,n-1);preorder(root);return 0;
}/*
6
4 2 1 5 3 6
1 2 3 4 5 6
*/