【PAT甲级 - C++题解】1138 Postorder Traversal

1138 Postorder Traversal

Suppose that all the keys in a binary tree are distinct positive integers. Given the preorder and inorder traversal sequences, you are supposed to output the first number of the postorder 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 N (≤ 50,000), the total number of nodes in the binary tree. The second line gives the preorder 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 first number of the postorder traversal sequence of the corresponding binary tree.

Sample Input:

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

Sample Output:

3

题意

给定前序遍历和中序遍历的结果，构建二叉树。

要求输出该二叉树的后序遍历结果的第一个元素值。

思路

1. 由于题目给定每个结点的值都不同，所以可以用哈希表存储每个结点在中序数组中的下标，方便后续使用。
2. 通过下标构建二叉树（其中 k-il-1 表示左子树结点个数）：

3. 因为构建二叉树的时候是先去递归左子树，所以第一个遍历到的结点就是二叉树最左边的那个点，而后序遍历结果的第一个点就是二叉树最左边的那个点，故只用在构建过程中记录一下即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int n;
int pre[N],in[N];
unordered_map<int,int> pos;
int post;
void build(int il,int ir,int pl,int pr)
{
    int root=pre[pl];
    int k=pos[root];
    if(il<k)    build(il,k-1,pl+1,pl+1+k-il-1);
    if(ir>k)    build(k+1,ir,pl+1+k-il-1+1,pr);
    if(!post)   post=root;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)    cin>>pre[i];    //输入前序数组
    for(int i=0;i<n;i++)    //输入中序数组，并记录每个元素的下标
    {
        cin>>in[i];
        pos[in[i]]=i;
    }
    build(0,n-1,0,n-1);
    cout<<post<<endl;
    return 0;
}