给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式:
输入第一行给出一个正整数N(<=30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式:
在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
输入样例: 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 输出样例: 4 1 6 3 5 7 2 #include <iostream> #include <queue> using namespace std; struct Node { int data; Node* lchlid; Node* rchild; }; Node* build_tree(int back[],int in[],int length) { if(length==0){ return NULL; } Node* temp = new Node;; int pos = 0; while(in[pos]!= back[length-1]){ pos++; } temp->data = in[pos]; temp->lchlid = build_tree(back,in,pos); temp->rchild = build_tree(back+pos,in+pos+1,length-pos-1); return temp; } bool first = true; void dfs(Node* root) //层次遍历 { queue<Node*> Q; Q.push(root); while(!Q.empty()){ Node* temp = Q.front(); if(first){ cout<<temp->data; first = false; } else { cout<<" "<<temp->data; } Q.pop(); if(temp->lchlid){ Q.push(temp->lchlid); } if(temp->rchild){ Q.push(temp->rchild); } } } int main() { int n; cin>>n; int back[n],in[n]; for(int i=0;i<n;i++){ cin>>back[i]; } for(int i=0;i<n;i++){ cin>>in[i]; } Node* root = build_tree(back,in,n); dfs(root); return 0; }