PAT甲级1138 Postorder Traversal

1138

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
结尾无空行

节点多达50000个，如果完整的构建二叉树再进行后序遍历的话后两个测试点会超时

所以不用构建二叉树，直接按照后序遍历的顺序进行。根据中序和先序找到根节点以及左右子树，找到左子树下最左边节点（如果没有那就是左子树中最右边节点）即后序遍历的第一个节点，然后输出。（这里的flag不能省略，在输出过后就无需进行遍历，否则会超时）

#include 
#include 
using namespace std;
vector pre;
vector in;
int n;
int flag = 0;
void postorder(int root,int start,int end){
    if(start > end||flag == 1){
        return;
    }
    int i = start;
    for(;i <= end;++i){
        if(pre[root] == in[i]){
            break;
        }
    }
    if(i != start){
        postorder(root + 1,start,i - 1);
    }
    if(i != end){
        postorder(i - start + root + 1,i + 1,end);
    }
    if(flag == 0){
        cout << in[i];
        flag = 1;
    }
    return;
}
int main(){
    cin >> n;
    pre.resize(n);
    in.resize(n);
    for(int i = 0;i < n;++i){
        cin >> pre[i];
    }
    for(int i = 0;i < n;++i){
        cin >> in[i];
    }
    postorder(0,0,n - 1);
    return 0;
}