题意：根据先序和后序求任意中序
思路：先序和中序或者后序和中序能够唯一确定一个二叉树，但是先序和后序遍历却不能唯一确定，题目中说任意打印一种情况即可，那剩下就是左子树和右子树划分的问题了
代码：
#include<iostream> #include<vector> using namespace std; vector<int> pre, in, 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 < pre.size() && pre[i] != post[postR-1])i++;//找到右子树的根节点 if (i - preL > 1) {//左子树不止一个节点时 getIn(preL + 1, i - 1, postL, postL + (i - 1 - (preL + 1)));//把左子树压入中序遍历中 } else { unique = false; } in.push_back(post[postR]);//把根节点压入中序遍历 getIn(i,preR, postL + (i - 1 - (preL + 1))+1,postR-1); //把以右子树压入中序遍历中 } } int main() { int n = 0; cin >> n; post.resize(n+1); pre.resize(n + 1); 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); if (unique) { cout << "Yes" << endl << in[0]; } else { cout << "No" << endl << in[0]; } for (int i = 1; i < in.size(); i++) { cout << " " << in[i]; } printf("\n"); system("pause"); return 0; }
