【wikioi】1029 遍历问题

题目链接：http://www.wikioi.com/problem/1029/

算法：DP

本题有个2小技巧。

1. 一棵二叉树的前序遍历a1a2a3...ai和后序遍历b1b2b3...bi有一种关系：当只有一棵子树的根 在a序列下标为i， 在b序列下标为b
   有  a[i-1] == b[j+1]
   这是因为当根只有一棵子树时，前序和后序遍历都是先遍历它的孩子，而且是唯一的一个孩子，所以相对位置是一样的。
2. 当确定了一棵树的前序和后序遍历时，可以得到用如上方法找到只有一棵子树的根，并且因为上面的性质，子树在为左子女还是右子女并不影响前序后序的顺序，但影响中序遍历的顺序，而可以假设子树为左子女也可以假设为右子女，那么我们得到：
   根据前后序得到中序遍历的数量 = 只有一个子女的根 ^ 2

那么答案就好求啦~

代码：

【wikioi】1029 遍历问题

原文：http://www.cnblogs.com/iwtwiioi/p/3538833.html