二叉树中序遍历问题

Question

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

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;
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;
}
非常感谢题主的指正