题目链接

Description
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
Sample Output:
3

思路：
经典根据二叉树的前序遍历和中序遍历建树问题，还可根据中序和后序建树，原理一样。
前序遍历的第一个值一定是根节点，根据此查找到中序遍历中根节点的位置(二叉树满足结点值各不相同的情况)，由此可将二叉树分为左子树，右子树，根结点，据此递归的去查找左子树和右子树的结点即可。
由于本题只要求输出后序遍历第一个结点值，考虑剪枝提高效率。

code:

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> preOrderSequence;
vector<int> inOrderSequence;
vector<int> postOrderSequence;

/*
 根据前序和中序得到后序遍历结果
 preL代表当前树前序遍历的左端点，preR代表当前树前序遍历的右端点
 inL代表当前树中序遍历的左端点，inR代表当前树中序遍历的右端点
 */
void getPostOrderSequence(int preL, int preR, int inL, int inR){
    if (postOrderSequence.size() != 0) return;//剪枝
    if (preL == preR) {
        postOrderSequence.push_back(preOrderSequence[preL]);
	return;
    }else if (preL > preR) return;
    
    int root = preOrderSequence[preL];//取出根节点的值
    //遍历查找 中序遍历中根节点的位置
    int pos;//指向中序遍历中根节点的位置
    for (pos = inL; pos <= inR; ++pos) {
        if (inOrderSequence[pos] == root) {
            break;
        }
    }
    int leftTreeNum = pos-inL;//左子树的结点个数
    
    getPostOrderSequence(preL+1, preL+leftTreeNum, inL, pos-1);//递归左子树
    getPostOrderSequence(preL+leftTreeNum+1, preR, pos+1, inR);//递归右子树
    postOrderSequence.push_back(root);
}

int main(){
    int N;
    cin >> N;
    preOrderSequence.resize(N);
    inOrderSequence.resize(N);
    
    //先输入preorder sequence
    for (int i = 0; i < N; ++i) {
        cin >> preOrderSequence[i];
    }
    
    //再输出inorder sequence
    for (int i = 0; i < N; ++i) {
        cin >> inOrderSequence[i];
    }
    
    //根据前序和中序建树
    getPostOrderSequence(0, N-1, 0, N-1);
    cout << postOrderSequence[0] << endl;

    return 0;
}