n个节点的二叉树有(2n)!/(n!*(n+1)!)

链接:https://www.nowcoder.com/questionTerminal/5feec2690f764b8699eab1f824610ddb
来源:牛客网

0个节点的二叉树有1种,即f(0)=1;1个节点的二叉树有1种,即f(1)=1;2个节点的二叉树有2种,即f(2)=2;3个节点的二叉树肯定先得固定一个根节点,然后还剩2个节点,这两个节点有三种排列方式,根节点左边两个、根节点左边一个右边一个、根节点右边两个,这样的话就可以用f(0),f(1)和f(2)来求了:f(3)=f(2)f(0)+f(1)f(1)+f(0)f(2)=21+11+12=5;同理f(4)=f(3)f(0)+f(2)f(1)+f(1)f(2)+f(0)f(3)=51+21+12+15=14;于是就有了递推公式:f(n)=f(n-1)*f(0)+f(n-2)*f(1)+···+f(1)*f(n-2)+f(0)f(n-1)。

声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。