PAT 甲级 1138 Postorder Traversal (25 分) 先序中序->后序

题意:

给定二叉树的先序遍历 中序遍历,输出后序遍历的第一个点

思路:

先序遍历中序遍历确定一棵二叉树,是一个递归的过程,然后再结合后序遍历这个递归过程,

可以知道:后序遍历的第一个结点是树的最左叶结点(也可能在根节点的右子树上)。

遍历可得

 

#include<bits/stdc++.h>
#include<cstring>
#define FI first
#define SE second

using namespace std;
typedef long long ll;
typedef pair<string, string> P;
const int maxn = 5e4 + 7;

int n, a[maxn], b[maxn];
map<int, int> pos;
int id = 1;
vector<int> ans;

void init(int l1, int r1, int l2, int r2) {
    //cout << l1 << " " << r1 << " + " << l2 << " " << r2 << endl;
    if(l1 > r1 || l2 > r2) return;
    if(l1 == r1) {
        ans.push_back(a[l1]);
        return;
    }
    int t = a[l1];
    int t1 = pos[t];
    int len = t1 - l2;
    init(l1+1, l1+len, l2, l2+len-1);
    if(ans.size()) return;
    init(l1+len+1, r1, l2+len+1, r2);
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
        pos[b[i]] = i;
    }
    init(1, n, 1, n);
    cout << ans[0] << endl;
    return 0;
}

 

上一篇:java面试知识点(最新)second


下一篇:51nod 1138 连续整数的和 好题