已知二叉树的后序和中序遍历求前序遍历

假设二叉树上各结点的权值互不相同且都为正整数。

给定二叉树的后序遍历和中序遍历，请你输出二叉树的前序遍历的最后一个数字。

输入格式:

第一行包含整数 N，表示二叉树结点总数。

第二行给出二叉树的后序遍历序列。

第三行给出二叉树的中序遍历序列。

输出格式

输出二叉树的前序遍历

数据范围

1≤N≤50000,
二叉树结点权值范围 [1,1e9]。

题解

众所周知，树的后序遍历最后一个数就是该树(子树)的 root 节点，我们每次只需要取后序遍历的最后一个节点就行~~

代码当中的build函数传递的分别是 一棵树(子树)后序遍历的左右闭区间 和 中序遍历的左右闭区间
这题比较难确定的是build函数中的第二个参数，也就是后序遍历的右区间
这里我们令其为 x ,下面我给出一个图来表示 x 的计算过程

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
unordered_map<int,int> l, r, c;
int build(int al, int ar, int bl, int br) // a 是后序， b 是中序
{
    int root = a[ar];   // 后序遍历的最后一个数 是该树的根节点, 子树也是
    int k = c[root];               // 

标签：遍历,后序,int,前序,二叉树,root,中序	

From： https://www.cnblogs.com/xxctx/p/18153071