大家好，欢迎来到IT知识分享网。
当n=0时，h(0)=1；
当n=1时，h(1)=1;
当n=2时，1个根节点固定，还有n-1=1个节点，可以作为左子树，也可以作为右子树，
即：h(2)=h(0)*h(1)+h(1)*h(0)=2；
当n=3时，1个根节点固定，还有n-1=2个节点，
即：h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5；
当n>=2时，可组成的二叉树数量为 h(n)=h(0)*h(n-1)+h(1)*h(n-2)+…+h(n-1)*h(0)种
符合Catalan数的定义，可直接利用通项公式得出结果。
递归式：
h(n)=h(n-1)*(4*n-2)/(n+1);
该递推关系的解为：
h(n)=C(2n,n)/(n+1)=P(2n,n)/(n+1)!=(2n)!/(n!*(n+1)!) (n=1,2,3,…)
相似的问题还有 NOIP2003普及组 出栈序列统计
转载于:https://www.cnblogs.com/Ro0kie/p/5185370.html
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/125199.html
