已知二叉树的先序和后序求任意一中序

假设一个二叉树上所有结点的权值都互不相同。

我们可以通过后序遍历和中序遍历来确定唯一二叉树。

也可以通过前序遍历和中序遍历来确定唯一二叉树。

但是，如果只通过前序遍历和后序遍历，则有可能无法确定唯一二叉树。

现在，给定一组前序遍历和后序遍历，请你输出对应二叉树的中序遍历。

如果树不是唯一的，则输出任意一种可能树的中序遍历即可。

输入格式

第一行包含整数 N，表示结点数量。

第二行给出前序遍历序列。

第三行给出后序遍历序列。

一行中的数字都用空格隔开。

输出格式

首先第一行，如果树唯一，则输出 Yes，如果不唯一，则输出 No。

然后在第二行，输出树的中序遍历。

注意，如果树不唯一，则输出任意一种可能的情况均可。

数据范围

1≤N≤30

输入样例1：

7
1 2 3 4 6 7 5
2 6 7 4 5 3 1

输出样例1：

Yes
2 1 6 4 7 3 5

输入样例2：

4
1 2 3 4
2 4 3 1

输出样例2：

No
2 1 3 4

题解

我们先说明下什么情况下会出现 树不唯一
设先序遍历的第一个元素下标是 al, 后序遍历的最后一个元素下标是 br ，那么当 al + 1 == br - 1的时候树不唯一 (ps: 理由如下图)

从上面的图中可以观察到 以3为根的子树下的4节点既可以树左子树又可以是右子树 (ps ： 不论是左子树还是右子树它的先序和后序遍历序列是相同的)

下面代码中 三个感叹号那里的两个 for 循环是 用来确定build的 先序和后序的左右闭区间的边界的

贴个图，大家一定看的懂

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
bool is_only = true;  //  树是否唯一的标志
int a[N], b[N];
unordered_map<int,int> l, r;
int build(int al, int ar, int bl, int br)   // a 先序, b 后序
{
    int root = a[al];
    if (al >= ar) return root;
    
    if (a[al + 1] == b[br - 1])    // 只要进这个分支就说明不唯一了
    {
        is_only = false;    
        l[root] = build(al + 1, ar, bl, br - 1);  // 这里假设是左子树
    }
    else
    {
        int ir, jr;    // ！！！

标签：遍历,后序,int,al,唯一,二叉树,先序	

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