一、题目描述

原题链接

Input Specification:

​​Output Specification:

Sample Input 1:

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

Sample Output 1:

Yes 2 1 6 4 7 3 5

Sample Input 2:

4 1 2 3 4 2 4 3 1

Sample Output 2:

No 2 1 3 4

二、解题思路

这道题考到了二叉树的遍历，需要我们对这些知识有比较好的理解。若要还原二叉树，没有中序遍历是不行的，因为这样的话，当某个结点只有一个孩子时，我们就没有办法确定是左子树还是右子树。这道题呢，我们将所有不确定的孩子都归为右孩子，递归处理得到中序遍历的序列。我们知道，先序遍历的第一个和后序遍历的最后一个一定是根结点，以当前后序遍历序列的倒数第二个结点为参考，寻找先序遍历中对应的数，如果在先序遍历中，这两个数不相邻，则说明我们可以区分开来左右子树，但是如果这两个数相邻，我们就没有办法区分左右，将变量unique设为false。这部分可以多搜一些其他的博客，笔者暂时还没有能力讲得特别清楚，非常抱歉。

三、AC代码

#include<iostream> #include<cstdio> #include<vector> using namespace std; vector<int> in, pre, post; bool unique = true; void getIn(int preL, int preR, int postL, int postR) { if(preL == preR) //递归边界 { in.push_back(pre[preL]); return; } if(pre[preL] == post[postR]) //找到根结点 { int i = preL + 1; while(i <= preR && pre[i] != post[postR-1]) i++; //以后序遍历的根结点的前一结点为参考，寻找其在前序中的位置 if(i - preL > 1) getIn(preL+1, i-1, postL, postL+(i-preL-1)-1); //可将左右子树分开 else unique = false; //无法分开左右子树 in.push_back(post[postR]); getIn(i, preR, postL+(i-preL-1), postR-1); //默认当作右子树处理 } } int main() { int n; scanf("%d", &n); pre.resize(n); post.resize(n); for(int i=0; i<n; i++) scanf("%d", &pre[i]); for(int i=0; i<n; i++) scanf("%d", &post[i]); getIn(0, n-1, 0, n-1); printf("%s\n%d", unique ? "Yes" : "No", in[0]); for(int i=1; i<in.size(); i++) printf(" %d", in[i]); printf("\n"); return 0; }