思路：中序遍历–根结点，左子树，右子树；后序遍历–左子树，右子树，根结点。 那么在找到根结点之后就可以开始划分左右子树了。左子树的先序第一个节点是根，左子树的后序最后一个节点是根。 例如 1 2 3 4 6 7 5 2 6 7 4 5 3 1 当前的根结点就是1，在先序中得到左子树的根结点就是2，再在后序中知道左子树的节点就是{2}，那么就得到左子树了，剩下的就是右子树。 如何判断重建的树是否唯一？非叶结点如果只有左子树或者右子树，那么就不唯一。 注意：如果你使用数组实现的二叉树，那么把数组开大一点，只开maxn=30+5的话第一组数据会WA（本人WA了半个小时才猜到这个套路），后来直接开10000过掉。
AC代码
#include <stdio.h> #include <string.h> const int maxn = 10000+5; bool isUnique; int pre[maxn], post[maxn]; int left[maxn], right[maxn]; int ans[maxn], nodes; //return root int reBuild(int prel, int prer, int postl, int postr) { if(prel > prer) return -1; int root = pre[prel]; if(prel == prer) { //leaf return root; } //left-tree int l1 = prel+1, r2; for(r2 = postl; r2 < postr; r2++) { if(post[r2] == pre[l1]) { break; } } int len = r2 - postl + 1; // check unique if(len == prer-prel) { isUnique = false; } int r1 = l1 + len -1; int l2 = postl; //rebulid left-tree left[root] = reBuild(l1, r1, l2, r2); //rebuild right-tree right[root] = reBuild(r1+1, prer, r2+1, prer-1); return root; } void getInorder(int root) { if(root == -1) return; getInorder(left[root]); ans[nodes++] = root; getInorder(right[root]); } int main() { int n; while(scanf("%d", &n) == 1) { isUnique = true; memset(left, -1, sizeof(left)); memset(right, -1, sizeof(right)); for(int i = 0; i < n; i++) { scanf("%d", &pre[i]); } for(int i = 0; i < n; i++) { scanf("%d", &post[i]); } int root = reBuild(0, n-1, 0, n-1); nodes = 0; getInorder(root); if(isUnique) { printf("Yes\n"); } else { printf("No\n"); } for(int i = 0; i < nodes; i++) { printf("%d%c", ans[i], i == nodes-1 ? '\n' : ' '); } } return 0; }如有不当之处欢迎指出！
