526互联

1020 Tree Traversals

发布时间 2023-04-20 18:12:04作者: 回忆、少年

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer  (), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
 

Sample Output:

4 1 6 3 5 7 2
 
 
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

const int N = 40;

int n,count1;
int postorder[N], inorder[N];               //后序遍历，中序遍历
unordered_map<int, int> l, r, pos;          //用哈希表模拟二叉树

int build(int il, int ir, int pl, int pr)
{
	if(il>ir||pl>pr) return -1; 
    int root = postorder[pr];
    int k = pos[root];                      //得到根节点在中序遍历中的下标

    //k大于il表示根节点左边还有节点，即当前根节点存在左子树，下同
    //下面两行是难点，举例解释见图
	if(il<k)l[root] = build(il, k - 1, pl, pl + k - 1 - il);
	if(ir>k)r[root] = build(k + 1, ir, pl + k - il, pr - 1);

    return root;
}

void bfs(int root)                          //BFS用来层序遍历输出
{
    queue<int> q;
    q.push(root);
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        if(t==-1)continue;
        if(count1==0)cout<<t;
        else cout <<" "<<t;
        count1++;
        if (l[t]) q.push(l[t]);       //判断该节点的左右儿子是否存在
        if (r[t]) q.push(r[t]);       //存在则加入队列，等待下一层遍历
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> postorder[i];
    for (int i = 0; i < n; i ++ )
    {
        cin >> inorder[i];
        pos[inorder[i]] = i;                //记录中序遍历每个点位置（剪枝）
    }

    int root = build(0, n - 1, 0, n - 1);   //参数为中序遍历区间和后序遍历区间
    bfs(root);

    return 0;
}