17年秋季第三题 PAT甲级 1138 Postorder Traversal (25分)

傷城~ 2023-07-13 03:22 127阅读 0赞

题目来源：[https://pintia.cn/problem-sets/994805342720868352/problems/994805345078067200][https_pintia.cn_problem-sets_994805342720868352_problems_994805345078067200]

备考汇总贴：[2020年3月PAT甲级满分必备刷题技巧][2020_3_PAT]

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: ###

# 题目分析（以下内容主要转载自[liuchuo][]，补充了讲解） #

1.前序中序转后序，因为输入并不复杂，所以采用的是不建树的遍历。由于递归遍历的顺序正好就是这道题要的顺序，直接在最后加个判断输出就行，真的很省力了。

2.只需要知道后序的第一个值，所以可以定义一个变量flag，当post的第一个值已经输出，则flag为true，递归出口处判断flag，可以提前return

# 满分代码 #

#include <iostream>
    #include <vector>
    using namespace std;
    vector<int> pre, in;
    bool flag = false;
    void postOrder(int prel, int inl, int inr) {
        if (inl > inr || flag == true) return;
        int i = inl;
        while (in[i] != pre[prel]) i++;
        postOrder(prel+1, inl, i-1);
        postOrder(prel+i-inl+1, i+1, inr);
        if (flag == false) {
            printf("%d", in[i]);
            flag = true;
        }
    }
    int main() {
        int n;
        scanf("%d", &n);
        pre.resize(n);
        in.resize(n);
        for (int i = 0; i < n; i++) scanf("%d", &pre[i]);
        for (int i = 0; i < n; i++) scanf("%d", &in[i]);
        postOrder(0, 0, n-1);
        return 0;
    }

[https_pintia.cn_problem-sets_994805342720868352_problems_994805345078067200]: https://pintia.cn/problem-sets/994805342720868352/problems/994805345078067200
[2020_3_PAT]: https://blog.csdn.net/allisonshing/article/details/104213959
[liuchuo]: https://blog.csdn.net/liuchuo/article/details/79064958