二叉树中序遍历问题

Question

给定一个n个节点的二叉树的中序遍历，输出有多少种可能的二叉树与之对应？
编程实现。

……………………………………………………………………………………
夜深人静的时候想起了她，然后写断代码压压惊

int f(int n)
{

int sum=0;
if(n==0||n==1)
    return 1;

for(int i=0;i<n;i++)
    sum+=f(i)*f(n-1-i);  
return sum;

}

Answer 1

f(0) = 1
f(1) = 1
...
f(n) = f(0) * f(n - 1) + f(1) * f(n - 2) + .. + f(n - 1) * f(0)

思路就是 对n个元素, 考虑每个元素为根节点的情况. 从f(2), f(3)... 向上计算到 f(n)

Answer 2

我的思路就是f(n-1)的来源是 (n-1)是Node(n)的父亲或者 Node(n)的右孩子， 所以有2个。
然后把n-1个结点分成两份，分别当 右孩子和父亲。
f(n) = 2*f(n-1) + ([f(n-2)*f(1)] + [f(n-3)*f(2)] + .. + [f(1)*f(n-2)]) (n >= 2)
f(0) = 0;
f(1) = 1;
f(2) = 2；
f(3) = 2*f(2) + 1*1 = 5;
f(4) = 2*f(3) + f(2)*f(1) + f(1)*f(2) = 14;

int f(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 0) {
        return 0;
    }
    int sum =  2 * f(n-1);
    int i;
    for (i = n - 2; i >= 0; i --) {
        sum += f(i)*f(n - 1 - i);
    }
    return sum;
}

非常感谢题主的指正