[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
所以 pre-order 的第一个元素一定等于 post-order 的最后一个元素. 然后在post-order中由前往后找, 找出等于pre-oder中第二个元素的位置, 也就是 left 的位置. 如果post-order中的这个位置不是倒数第二个, 说明左右子树都非空, 那么对左右子树递归调用后用乘法原理. 如果是倒数第二个, 说明有一个子树为空, return的值就是 2*递归调用非空子树.

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);

}

依次查看前序和后序中长度为 0 到 n - 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];
}
Read full article from [itint5]根据前序后序遍历统计二叉树 - 阿牧遥 - 博客园