题意:
给定二叉树的先序遍历 中序遍历,输出后序遍历的第一个点
思路:
先序遍历中序遍历确定一棵二叉树,是一个递归的过程,然后再结合后序遍历这个递归过程,
可以知道:后序遍历的第一个结点是树的最左叶结点(也可能在根节点的右子树上)。
遍历可得
#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;
}