根据前序遍历和后序遍历确定二叉树形态数

#include <stdio.h>

long long int countTrees(char pre[], char post[], int preStart, int preEnd, int postStart, int postEnd)
{
    // Base case
    if (preStart > preEnd || postStart > postEnd)
        return 1;

    // The first character in the pre[] is the root of the tree
    char root = pre[preStart];
    int i, j, k;

    // Search the index of the root in post[]
    for (i = postStart; i <= postEnd; i++)
    {
        if (post[i] == root)
            break;
    }

    long long int left = 0, right = 0;

    // Count all possible left subtrees
    for (j = preStart + 1, k = postStart; j <= preEnd; j++)
    {
        if (k <= postEnd && pre[j] == post[k])
        {
            left++;
            k++;
        }
    }

    // Count all possible right subtrees
    for (j = preStart + 1, k = i + 1; j <= preEnd; j++)
    {
        if (k <= postEnd && pre[j] == post[k])
        {
            right++;
            k++;
        }
    }

    // Recursively count the number of trees
    long long int total = (left + 1) * (right + 1);

    // Count trees in the left and right subtrees
    total += countTrees(pre, post, preStart + 1, preStart + left, postStart, postStart + left - 1);
    total += countTrees(pre, post, preStart + left + 1, preEnd, postStart + left, postEnd - 1);

    return total;
}

int main()
{
    char pre[1001], post[1001];
    scanf('%s', pre);
    scanf('%s', post);

    int n = 0;
    while (pre[n] != '\0')
        n++;

    long long int count = countTrees(pre, post, 0, n - 1, 0, n - 1);
    printf('%lld\n', count);

    return 0;
}

代码解析：

这是一个递归的解法，通过前序遍历和后序遍历的顺序来确定二叉树的形态。参数 preStart 和 preEnd 表示前序遍历数组的起始和结束位置，postStart 和 postEnd 表示后序遍历数组的起始和结束位置。

递归的过程中，首先找到根节点在后序遍历数组中的位置，然后根据根节点的位置将前序遍历数组分为左子树和右子树的部分。然后分别递归计算左子树和右子树的形态数目，并将左子树和右子树的形态数目相乘，得到当前二叉树的形态数目。最后将左子树和右子树的形态数目加起来，得到所有二叉树的形态数目。