## Friday, November 27, 2015

### [itint5]根据前序后序遍历统计二叉树 - 阿牧遥 - 博客园

[itint5]根据前序后序遍历统计二叉树 - 阿牧遥 - 博客园
链接: http://www.itint5.com/oj/#28
问题:
对于包含n个结点的二叉树（树中结点编号从1到n），已知前序和后序遍历序列，
我们知道不一定能唯一的恢复这棵树。请计算出满足条件的二叉树的总数。
样例：
前序遍历序列preorder：1 2
后序遍历序列postorder：2 1
一共有2棵满足条件的二叉树：
1       1
/         \
2           2
Solution: 递归和动态规划都可以完成。这题效率上来讲还是top-down的递归快一些。

pre-order: root, left *************, right #########
post-order: **************left, ########right, root

`int` `countHelper(vector<``int``>& preorder, vector<``int``>& postorder, ``int` `preA, ``int` `preB, ``int` `postA, ``int` `postB) {`
`    ``if` `(preA > preB || postA > postB) ``return` `0;`
`    ``if` `(preA == preB && postA == postB && preorder[preA] == postorder[postB]) ``return` `1;`
`    ``// preB > preA && postB > postA`
`    ``// assert(preorder[preA] == postorder[postB]`

`    ``if` `(preorder[preA+1] == postorder[postB-1]) { ``// right tree or left tree is null`
`        ``return` `2 * countHelper(preorder, postorder, preA+1, preB, postA, postB-1);`
`    ``} ``else` `{ ``// right tree and left tree both exists`
`        ``int` `rightInPreOrder = -1;`
`        ``for` `(``int` `i = preA+2; i < preorder.size(); i++) {`
`            ``if` `(preorder[i] == postorder[postB-1]) {`
`                ``rightInPreOrder = i;`
`                ``break``;`
`            ``}`
`        ``}`
`        ``int` `leftInPostOrder = -1;`
`        ``for` `(``int` `i = postB-2; i >= 0; i--) {`
`            ``if` `(postorder[i] == preorder[preA+1]) {`
`                ``leftInPostOrder = i;`
`                ``break``;`
`            ``}`
`        ``}`
`        ``return` `countHelper(preorder, postorder, preA+1, rightInPreOrder-1, postA, leftInPostOrder) *`
`               ``countHelper(preorder, postorder, rightInPreOrder, preB, leftInPostOrder+1, postB-1);`
`    ``}`
`    `
`}`

`int` `countValidTrees(vector<``int``>& preorder, vector<``int``>& postorder) {`
`    ``// assert(preorder.size() == postorder.size());`
`    ``return` `countHelper(preorder, postorder, 0, preorder.size()-1, 0, postorder.size()-1);`
`}`

def countValidTrees(self, preorder, postorder): if len(preorder) != len(postorder): return -1 return self.findCnt(preorder, postorder) def findCnt(self, preorder, postorder): if len(preorder) == 0: return 1 if preorder[0] != postorder[-1]: return -1 cnt = 0 for k in range(len(preorder)): leftCnt = self.findCnt(preorder[1: 1 + k], postorder[:k]) if leftCnt == -1: continue rightCnt = self.findCnt(preorder[1 + k:], postorder[k:-1]) if rightCnt == -1: continue else: cnt += leftCnt * rightCnt return cnt
https://github.com/AnnieKim/ITint5/blob/master/028_%E6%A0%B9%E6%8D%AE%E5%89%8D%E5%BA%8F%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E7%BB%9F%E8%AE%A1%E4%BA%8C%E5%8F%89%E6%A0%91.cpp
方案一：递归。
int countValidTreesRe(vector<int>& preorder, int i, vector<int>& postorder, int j, int N) {
if (N == 0) return 1;
if (preorder[i] != postorder[j+N-1]) return -1;
int count = 0;
for (int k = 0; k < N; ++k)
{
int left = countValidTreesRe(preorder, i+1, postorder, j, k);
if (left == -1) continue;
int right = countValidTreesRe(preorder, i+1+k, postorder, j+k, N-1-k);
if (right == -1) continue;
count += left * right;
}
return count;
}

int countValidTrees(vector<int>& preorder, vector<int>& postorder) {
if (preorder.size() != postorder.size()) return false;
int N = preorder.size();
return countValidTreesRe(preorder, 0, postorder, 0, N);
}

方案二：dp。
int countValidTrees(vector<int>& preorder, vector<int>& postorder) {
if (preorder.size() != postorder.size()) return false;
int N = preorder.size();
int dp[N+1][N+1][N+1];
for (int k = 0; k <= N; ++k)
for (int i = 0; i <= N-k; ++i)
for (int j = 0; j <= N-k; ++j)
{
dp[k][i][j] = 1;
if (k == 0) continue;
if (preorder[i] != postorder[j+k-1]) {
dp[k][i][j] = -1;
continue;
}
dp[k][i][j] = 0;
for (int l = 0; l < k; ++l)
if (dp[l][i+1][j] != -1 && dp[k-1-l][i+1+l][j+l] != -1)
dp[k][i][j] += dp[l][i+1][j] * dp[k-1-l][i+1+l][j+l];
}
return dp[N][0][0];
}