题目描述

y总的这道题解的的太巧妙了，看了好长时间脑壳疼，虽然能做出来，但思路依然不通畅，我等凡人还是理解力差了点Q.Q
现在给出我的解法，希望能帮到在这里感到困惑的同学

思考过程：
首先preorder的第一个节点和postorder的最后一个节点一定是根节点root。preorder的第二个节点preorder[2]要么是左子树根节点，要么是右子树根节点（当左子树不存在）；postorder的倒数第二个节点postorder[-2]要么是右子树根节点，要么是左子树根节点（当右子树不存在）。

1. 如果preorder[2]!=postorder[-2]，那就说明preorder[2]和postorder[-2]所代表地根节点不是同一棵树，因此存在左子树和右子树，从而preorder[2]是左子树根节点，postorder[-2]是右子树根节点。
2. 如果preorder[2]==postorder[-2]，那么就说明只存在一边的子树，那么这个时候你思考一下，其实是只有左子树也可以，只有右子树也可以。所以，存在不同的树的根源就在于这里。

那么我们就可以递归地去判断，只要存在一次preorder[2] == postorder[-2]，就说明有多个解，这个时候我们只构造左子树（或右子树）就行了。


所以其实我们可以看出一个规律：只有满二叉树才能通过前序遍历和后序遍历唯一确定

算法思路：
先通过前序遍历和后序遍历的序列来构造二叉树，如果存在在不同的选择，默认选择构造左子树。最后进行中序遍历

样例

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 40;
int l[N],r[N];  //l[i],r[i]代表i号节点的左右儿子
int post[N], pre[N]; //后续遍历和前序遍历的序列
bool is_only = true;  //全局变量，是否为唯一二叉树的标志
int in[N], cnt = 0;

//根据pre[l1,r1], post[l2,r2]创建二叉树节点，并分配左右儿子指针
int build(int l1, int r1, int l2, int r2)
{
    int root = pre[l1];

    if(l1 == r1) return root;
    //根据pre[l1+1] 和 post[r2-1]来判断答案是否为1
    if(pre[l1+1] == post[r2-1]) //说明答案不唯一，我们直接认为右儿子不存在即可
        l[root] = build(l1+1, r1, l2, r2-1), is_only = false;
    else  //不相同，那么说明 pre[l1+1]为左儿子的根节点， post[r2-1]为右儿子根节点
    {
        int lpre, rpost; //lpre代表前序序列中左子树的右边界，rpost代表后序序列中右子树的左边界
        for(lpre = l1+1;lpre<=r1;lpre++) if(pre[lpre] == post[r2-1]) break;
        for(rpost = r2-1;rpost>=l2;rpost--) if(post[rpost] == pre[l1+1]) break;
        lpre--, rpost++;
        l[root] = build(l1+1, lpre, l2, rpost-1);
        r[root] = build(lpre+1, r1, rpost, r2-1);
    }

    return root;
}

//中序遍历
void inorder(int root)
{
    if(l[root] != -1) inorder(l[root]);
    in[cnt++] = root;
    if(r[root] != -1) inorder(r[root]);
}

int main()
{
    //用-1来来代表儿子节点为空
    memset(l,-1,sizeof(l));
    memset(r,-1,sizeof(r));
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> pre[i];
    for(int i=0;i<n;i++)
        cin >> post[i];

    //根据前序遍历和后序遍历创建二叉树
    int root = build(0,n-1,0,n-1);

    if(is_only) puts("Yes");
    else puts("No");
    inorder(root);

    cout << in[0];
    for(int i=1;i<n;i++)
        cout << " " <<in[i];
}