二叉树中序遍历问题

Question

给定一个n个节点的二叉树的中序遍历，输出有多少种可能的二叉树与之对应？编程实现。
……………………………………………………………………………………夜深人静的时候想起了她，然后写断代码压压惊
intf(intn){
intsum=0;
if(n==0||n==1)
return1;
for(inti=0;isum+=f(i)*f(n-1-i);
returnsum;
}

Answer 1

f(0)=1f(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;intf(intn){if(n==1){return1;}if(n==0){return0;}intsum=2*f(n-1);inti;for(i=n-2;i>=0;i--){sum+=f(i)*f(n-1-i);}returnsum;}非常感谢题主的指正