PAT甲级-1020 Tree Traversals

题目

题目大意

给出一棵树的后序遍历和中序遍历，要求输出该树的层序遍历。

思路

非常典型的树的构建与遍历问题。后序遍历和中序遍历可以得出一个树的结构，用递归锁定根节点，然后再遍历左右子树，我之前发过类似题目的博客，这里就不再详细赘述。层序遍历就是使用队列了。

代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;int n;
vector<int> hou, mid, level;
struct node{int data;node * lchild, *rchild;
};void buildtree(node * &root, int hl, int hr, int ml, int mr){if (hl > hr || ml > mr){return;}int pos;for (int i = ml; i <= mr; i++){if (hou[hr] == mid[i]){pos = i;break;}}root = new node();root->data = hou[hr];root->lchild = root->rchild = nullptr;buildtree(root->lchild, hl, hl + pos - ml - 1, ml, pos - 1);buildtree(root->rchild, hl + pos - ml, hr - 1, pos + 1, mr);
}void findlevel(node * root){queue<node *> q;q.push(root);while (!q.empty()){node * now = q.front();level.push_back(now->data);q.pop();if (now->lchild) q.push(now->lchild);if (now->rchild) q.push(now->rchild);}
}int main(){cin >> n;hou.resize(n);mid.resize(n);for (int i = 0; i < n; i++){cin >> hou[i];}for (int i = 0; i < n; i++){cin >> mid[i];}node * root = nullptr;buildtree(root, 0, n - 1, 0, n - 1);findlevel(root);for (int i = 0; i < (int)level.size(); i++){if (i != 0) cout << " ";cout << level[i];}cout << endl;return 0;
}