大家好，又见面了，我是全栈君。
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：
输入第一行给出一个正整数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<algorithm> #include<iostream> #include<cstdio> #include<vector> #include<set> #include<queue> using namespace std; const int N = 50 + 5; struct node{ int key, lchild, rchild; node(){ lchild = rchild = 0; } }Node[N]; vector<int> post, in; int n, key, st; void DFS(int &root, int ls, int lt, int is, int it){ if(root == 0) root = ++st; int p = post[lt]; Node[root].key = p; int pos = is; while(in[pos] != p) pos++; if(pos != is){ DFS(Node[root].lchild, ls, ls + pos - is - 1, is, pos - 1); } if(pos != it){ DFS(Node[root].rchild, ls + pos - is, lt - 1, pos + 1, it); } } void BFS(int root){ int cnt = 0; queue<int> Q; Q.push(root); while(!Q.empty()){ int tmp = Q.front(); Q.pop(); printf("%d%c", Node[tmp].key, ++cnt == n?'\n':' '); if(Node[tmp].lchild){ Q.push(Node[tmp].lchild); } if(Node[tmp].rchild){ Q.push(Node[tmp].rchild); } } } int main(){ scanf("%d", &n); for(int i = 0; i < n; i++){ scanf("%d", &key); post.push_back(key); } for(int i = 0; i < n; i++){ scanf("%d", &key); in.push_back(key); } int root = 0; st = 0; DFS(root, 0, n-1, 0, n-1); BFS(root); }
转载于:https://www.cnblogs.com/Pretty9/p/8623828.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107626.html原文链接：https://javaforall.net
