-
2017-09-28 13:54:47
N个节点的二叉树有多少种形态
这是一道阿里的面试题。其实算不上新鲜，但是我之前没关注过，如今碰到了，就顺便探讨下这个问题吧：）
拿到这个题，首先想到的是直接写出表达式肯定不行，所以有必要从递推入手。由特殊到一般，归纳法么~而且二叉树离不开递推这个尿性。。。
先考虑只有一个节点的情形，设此时的形态有f(1)种，那么很明显f(1)=1
如果有两个节点呢？我们很自然想到，应该在f(1)的基础上考虑递推关系。那么，如果固定一个节点后，有两种情况，一是左子树还剩一个节点，此刻类型数量为f(1)，第二种情况是右子树生一个节点，此刻类型数量为f(1)，固有f(2) = f(1) + f(1)
如果有三个节点呢？我们需要考虑固定两个节点的情况么？当然不行，为什么？
因为当节点数量大于等于2时，无论你如何固定，其形态必然有多种，而在这多种基础之上你如何安排后续剩下的节点呢？所以必须挑出这个误区。
回到二叉树的定义，二叉树本质上就是一个递归的形式，左子树，右子树，根节点。所以根节点应该不变，需要递归处理的是左右子树。
也就是说，还是考虑固定一个节点，即根节点。好的，按照这个思路，还剩2个节点，那么左右子树的分布情况为2=0+2=1+1=2+0。
所以有3个节点时，递归形式为f(3)=f(2) + f(1)*f(1) + f(2). (注意这里的乘法，因为左右子树一起组成整棵树，根据排列组合里面的乘法原理即可得出)
那么有n个节点呢？我们固定一个节点，那么左右子树的分布情况为n-1=n-1 + 0 = n-2 + 1 = ... = 1 + n-2 = 0 + n-1
OK。递归表达式出来了f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + ... + f(1)f(n-2) + f(n-1)
观察一下这个表达式，嗯，和我们之前见过的递归表达有一点区别，递推层级为n的时候，更多的是考虑前一步(n-1)，或者前两步(n-1)和(n-2)。
但是这里却考虑到所有的情况，即1到n-1。
最后说明一下，这个表达式有一个学名，叫做Catalan数。上面我们没有定义f(0)。如果把f(0)也考虑进去，显然没有节点也只有一种情况，即f(0)=1
标准表达式为f(n) = f(n-1)f(0) + f(n-2)f(1) + f(n-3)f(2) + ... + f(1)f(n-2) + f(n-1)f(0)
前几个数为1,1,2,5,14,42,132。
此外，还有一个通项公式为1/(n+1) * C(n, 2n) = C(n, 2n) - C(n-1, 2n) , n = 0,1,2,...
有兴趣的同学可以参考组合数学相关书籍，这里就不累述其证明和推导了。
更多相关内容 -
n个节点的二叉树有多少种形态（Catalan数）
2021-08-01 19:16:03（1）先考虑只有一个节点的情形，设此时的形态有f(1)种，那么很明显f(1)=1 （2）如果有两个节点呢？我们很自然想到，应该在f(1)的基础上考虑递推关系。那么，如果固定一个节点后，左右子树的分布情况为1=1+0=0+1，...展开全文分析过程：
（1）先考虑只有一个节点的情形，设此时的形态有f(1)种，那么很明显f(1)=1（2）如果有两个节点呢？我们很自然想到，应该在f(1)的基础上考虑递推关系。那么，如果固定一个节点后，左右子树的分布情况为1=1+0=0+1，故有f(2) = f(1) + f(1)
（3）如果有三个节点，（我们需要考虑固定两个节点的情况么？当然不，因为当节点数量大于等于2时，无论你如何固定，其形态必然有多种）我们考虑固定一个节点，即根节点。好的，按照这个思路，还剩2个节点，那么左右子树的分布情况为2=2+0=1+1=0+2。
所以有3个节点时，递归形式为f(3)=f(2) + f(1)*f(1) + f(2)。(注意这里的乘法，因为左右子树一起组成整棵树，根据排列组合里面的乘法原理即可得出)（4）那么有n个节点呢？我们固定一个节点，那么左右子树的分布情况为n-1=n-1 + 0 = n-2 + 1 = … = 1 + n-2 = 0 + n-1。此时递归表达式为f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(n-1)
接下来我们定义没有节点的情况，此时也只有一种情况，即f(0)=1
那么则有:
f(0)=1，f(1)=1
f(2)=f(1)f(0)+f(0)f(1)
f(3)=f(2)f(0)+f(1)f(1)+f(0)f(2)
.
f(n)=f(n-1)f(0)+f(n-2)f(1)+……….+f(1)f(n-2)+f(0)f(n-1)
该数列称为卡特兰数（Catalan数），该递推关系的解为：
即含n个节点的二叉树有f(n)种形态。【其他使用Catalan数解决的问题】
(1)矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
(2)一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
(3)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
(4)将一个凸多边形区域分成三角形区域的方法数?
(5)在圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。
(6)一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
-
n个节点的二叉树有多少种形态
2019-07-29 11:59:19（1）先考虑只有一个节点的情形，设此时的形态有f(1)种，那么很明显f(1)=1 （2）如果有两个节点呢？我们很自然想到，应该在f(1)的基础上考虑递推关系。那么，如果固定一个节点后，左右子树的分布情况为1=1+0=0+1，...展开全文分析过程：
（1）先考虑只有一个节点的情形，设此时的形态有f(1)种，那么很明显f(1)=1（2）如果有两个节点呢？我们很自然想到，应该在f(1)的基础上考虑递推关系。那么，如果固定一个节点后，左右子树的分布情况为1=1+0=0+1，故有f(2) = f(1) + f(1)
（3）如果有三个节点，（我们需要考虑固定两个节点的情况么？当然不，因为当节点数量大于等于2时，无论你如何固定，其形态必然有多种）我们考虑固定一个节点，即根节点。好的，按照这个思路，还剩2个节点，那么左右子树的分布情况为2=2+0=1+1=0+2。
所以有3个节点时，递归形式为f(3)=f(2) + f(1)*f(1) + f(2)。(注意这里的乘法，因为左右子树一起组成整棵树，根据排列组合里面的乘法原理即可得出)（4）那么有n个节点呢？我们固定一个节点，那么左右子树的分布情况为n-1=n-1 + 0 = n-2 + 1 = … = 1 + n-2 = 0 + n-1。此时递归表达式为f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(n-1)
接下来我们定义没有节点的情况，此时也只有一种情况，即f(0)=1
那么则有:
f(0)=1，f(1)=1
f(2)=f(1)f(0)+f(0)f(1)
f(3)=f(2)f(0)+f(1)f(1)+f(0)f(2)
.
.
.
.
f(n)=f(n-1)f(0)+f(n-2)f(1)+……….+f(1)f(n-2)+f(0)f(n-1)
该数列称为卡特兰数（Catalan数），该递推关系的解为：
即含n个节点的二叉树有f(n)种形态。前几项为: 1, 1, 2, 5, 14, 42, 132,....
# 求n个节点的二叉树有多少种形态 class Solution: def orderMultiply(self, x): if x == 0: return 1 else: return x * self.orderMultiply(x-1) def getStateofBinaryTree(self, n): if n == 0: return elif n == 1: return 1 else: return self.orderMultiply(2*n) / self.orderMultiply(n) / self.orderMultiply(n+1) n = 3 answer = Solution() print(answer.getStateofBinaryTree(n))【其他使用Catalan数解决的问题】
(1)矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
(2)一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
(3)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
(4)将一个凸多边形区域分成三角形区域的方法数?
(5)在圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。
(6)一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？转自 :
1 https://blog.csdn.net/adminabcd/article/details/46672759
2 http://www.cnblogs.com/ShaneZhang/p/4102581.html
3 http://www.cppblog.com/MiYu/archive/2010/08/07/122573.html
-
n个结点的二叉树一共有多少种形态
2021-07-13 14:34:13=2）的二叉树有，求和的每一项，分别表示根的左子树为m个节点、右子树为 n-1-m个节点的情况。（总共n个节点，左子树m个节点，根节点有1个，那么右子树的节点数为n-1-m个） 刚好就是catalan数，直接用catalan数的公式...展开全文记n个节点的二叉树形态个数为A[n]
1）0个节点的二叉树只有1种形态，A[0]=0；1个节点的二叉树只有1种形态，A[1]=12）n个节点（n>=2）的二叉树有
，求和的每一项，分别表示根的左子树为m个节点、右子树为 n-1-m个节点的情况。（总共n个节点，左子树m个节点，根节点有1个，那么右子树的节点数为n-1-m个）
刚好就是catalan数，直接用catalan数的公式：h(n)==
-
为什么n个节点的二叉树是卡特兰数
2021-01-07 17:53:14对于n个节点的二叉树，我们把这n个都当作父亲节点，一定可以补充（n+1）个叶子节点，使之成为一棵（2n+1）个节点的完全二叉树。我们把原来的二叉树称作父亲树，即全是父亲节点的树。 一棵父亲树一定与一棵完全二叉树... -
具有n个节点的二叉树有多少种形态
2018-11-02 21:05:37【n个节点的二叉树有多少种形态（Catalan数）】 分析过程： （1）先考虑只有一个节点的情形，设此时的形态有f(1)种，那么很明显f(1)=1 （2）如果有两个节点呢？我们很自然想到，应该在f(1)的基础上考虑递推关系。... -
N个节点二叉树有多少种形态
2014-09-28 15:07:151个节点的二叉树只有1种形态，A[1]=1 2）n个节点（n>=2）的二叉树有 A[n] = ∑ [m=0到n-1] ( A[m]*A[n-m-1] ) ，求和的每一项，分别表示根的左子树为m个节点、右子树为 n-m-1个节点的情况 刚好就是catalan数，直接用... -
按照二叉树的定义，4个节点的二叉树有多少种？
2020-08-18 15:04:47n个节点的二叉树有(2n)!...3个节点的二叉树肯定先得固定一个根节点，然后还剩2个节点，这两个节点有三种排列方式，根节点左边两个、根节点左边一个右边一个、根节点右边两个，这样的话就可以用f(0),f -
具有N个节点的二叉树有多少种形态，居然有计算公式
2017-09-07 10:34:11具有3个结点的二叉树有几种形态？ 正确答案: B 你的答案: B (正确) 4 5 6 7 解析 这是一道牛客网上的测试题，因为题目是求3个节点的二叉树的形态，所以直接手画了。... -
n个结点下，可构成多少种不同形态的二叉树
2020-05-10 11:41:29n个结点下，可构成多少种不同形态的二叉树 先来回顾下“树的定义”中的部分描述： 树是由唯一的根和若干棵互不相交的子树组成的。其中，每一棵子树又是一棵树，也是由唯一的根结点和若干颗互不相交的子树组成的。... -
N个节点的二叉树有多少种形态（卡特兰数）
2018-05-16 20:12:00N个节点的二叉树有多少种形态 这是一道阿里的面试题。其实算不上新鲜，但是我之前没关注过，如今碰到了，就顺便探讨下这个问题吧：） 拿到这个题，首先想到的是直接写出表达式肯定不行，所以有必要从递推入手。... -
n个节点的二叉树，最多可以有多少层？ D
2021-01-25 23:24:201.n个节点的二叉树，最多可以有多少层？ A.n/2 B.log(n) C.n-1 D.n 答案解析： D 假设从根节点开始，根节点的层数为1，每一层一个节点，则有n层。 -
教你一秒钟得出 N个节点的完全二叉树有多少个叶子节点 / 度为1或2的节点个数
2020-02-29 19:46:00没耐心的同学们可以直接拉到最底下看结论，有兴趣的话可以浏览全篇文章 ...一棵完全二叉树具有1000个结点，则此完全二叉树有多少个度为2的结点？ 完全二叉树699个节点，则叶子节点有多少个？ 已知完全二叉树... -
n个节点二叉树有几个指针域_java在二叉树的每个节点中填充下一个右指针
2020-09-01 20:15:07n个节点二叉树有几个指针域Problem Statement: You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. Populate each next pointer to point to its ... -
求N个结点能够组成的二叉树的个数
2022-05-04 20:51:35求N个结点能够组成的二叉树的个数 -
递归算法计算n个结点的二叉树的形态数
2021-11-16 21:35:47如：3个结点的二叉树共有五种不同形态，即n=3时，k=5。 算法思想：本题与求二叉树结点所在层数类似，通过递归算法求出以左右孩子结点为根结点的树的形态树，然后相乘即为该结点的形态数。 递归公式为：sum+=count_... -
n个节点组成二叉树的形态有几种
2014-04-07 15:22:52n个节点n组成的二叉树 -
具有n个结点且深度也为n的二叉树有多少种？
2015-11-30 09:37:04如题，考研数据结构问题，具有n个结点且深度也为n的二叉树有多少种？ -
n个节点能组成多少种二叉树
2014-08-29 09:48:13种形态的二叉树，令 n 个节点可组成的二 叉树数量表示为 h(n) ， 则 h(1)=1; 当 n=2 时， 1 个根节点固定，还有 n-1 个节点，可以作为左子树，也可以作为右子树， 即： h(2)=h(0)*h(1... -
【数据结构】线索二叉树中为什么n个结点的二叉树中，有n+1和空指针
2020-12-13 21:23:46线索二叉树中为什么n个结点的二叉树中，有n+1和空指针： 因为每个叶结点有2个空指针，而每个度为1的结点有1个空指针， 则总的空指针数为 2 * n0 + n1 而 n0 = n2 + 1 (二叉树的特性) 所以对上式化简，德总的空... -
完全二叉树的种类(动态规划\备忘录方法\Catalan数\C++实现)
2012-11-01 15:17:23构造n个(2<=n)叶结点的的完全二叉树(完全二叉树意味着每个分支结点都有2个儿子结点),有多少种构造方法? 注意:不改变n个结点的相对顺序,左右儿子不调换. 例如: 4个叶子节点A1,A2,A3,A4，可构造出如下完全二叉树，共... -
高度为n的平衡二叉树最少需要多少个节点？
2020-09-01 07:47:31高度为n的平衡二叉树最少需要多少个节点？高度为n的平衡二叉树最少需要多少个节点？参考 高度为n的平衡二叉树最少需要多少个节点？ 设f（n）为高度为n的平衡二叉树最少含有的节点数，则：f(1) = 1;f(2) = 2; f(3) = ... -
二叉树n个结点的深度求法
2022-04-08 21:12:51一棵二叉树有n个结点。 该树满足任意结点的左子树结点个数和右子树的结点个数之差最多为1。 因为 2^n-1是表示n层满二叉树的结点总数 所以 2^n-1>=二叉树的结点总数 若结点为2022,则树的最大深度是? 2^10=... -
N个结点不同结构的二叉树个数
2018-06-17 01:35:56求n个无差别的节点构成的二叉树有多少种不同的结构？给定一个整数n，请返回不同结构的二叉树的个数。保证结果在int范围内。测试样例：1返回：1class TreeCount {public: int Cmn(int m,int n) { if(m==n||n==0) ... -
求证：具有 n 个结点的完全二叉树的深度为......
2021-10-13 23:55:29证明：设完全二叉树的深度为h，则依据“深度为h的二叉树至多有2h-1个结点（h≥1）”的性质，可得：2^(h-1)-1＜n ≤ 2^h-1 其等价于 2^(h-1)＜n +1 ≤ 2^h ，也即 2^(h-1) ≤ n^h ● 对式子 2^(h-1)＜n +1 ≤ 2^h 求... -
4个结点组成的二叉树有__不同的形态
2022-04-29 23:34:15我们固定根节点，那么剩下两个结点我们可以分配给左右子树，分别有三种情况 左子树两个右子树零个 左右子树分别一个 右子树两个左子树一个 那么f(3) = f(2)*f(0)+f(1)*f(1)+f(0)*f(2) 那么f(0)是多少呢，没有
