注意new node 必须写 申请地址空间
Node * root = new Node();//可以 struct Node* root;//不行 //给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。 //这里假设键值都是互不相等的正整数。 #include <iostream> #include <cstdio> #include <queue> #include <vector> using namespace std; vector<int> v; int post[50],in[50]; struct Node{ int data; Node* lchild; Node* rchild; }; Node* createTree(int postL,int postR,int inL,int inR){//后序 中序 if(postL>postR)return NULL; int index; //struct Node node; Node* root = new Node; root->data=post[postR]; for(int i=inL;i<=inR;i++){ if(in[i]==post[postR]){ index=i; break; } } int leftNum=index-inL;//3 //2 3 1 5 7 6 |4(root)| //1 2 3 |4(root)| 5 6 7----------------------------- //2 3 1|| 5 7 6 |4(root)|---------------------------- //1(root) 2 3 |4(root)| 5 6(root) 7 root->lchild=createTree(postL,postL+leftNum-1,inL,index-1);//postL,postL+leftNum-1,inL,index-1 root->rchild=createTree(postL+leftNum,postR-1,index+1,inR);//postL+leftNum,postR-1,index+1,inR return root; } void bfs(Node* node){ queue<Node*> q; q.push(node); while(!q.empty()){ Node* tmp=q.front(); q.pop(); v.push_back(tmp->data); if(tmp->lchild!=NULL)q.push(tmp->lchild); if(tmp->rchild!=NULL)q.push(tmp->rchild); } } int main() { int n; cin>>n; for(int i=0;i<n;i++){ scanf("%d",&post[i]); } for(int i=0;i<n;i++){ scanf("%d",&in[i]); } Node* root=createTree(0,n-1,0,n-1);//后序，中序 bfs(root); for(int i=0;i<v.size();i++){ if(i==0) cout<<v[i]; else cout<<" "<<v[i]; } return 0; }