能否讲一下卡特兰数，我自己理解的不太透彻，看一遍很快就忘记了。

Question

对应的面试题应该是，给定一定数量的节点，问可以构造出多少种二叉树。

Answer 1

triump 2019-02-27 00:04:44

其实就是一个组合数学里最基本的乘法原理(分步)与加法原理（分类）的一个复合.
设f(n) 为n 个节点所构成的不同结构二叉树的总数.
则 f(n) = f(0)*f(n-1) + f(1)*f(n-2)+ f(2)*f(n-3) + .........f(n-1) * f(0)
其中f(0) = 1 f(1) = 1.
这个就是卡特兰数的递推关系.
可以这样理解，n 个节点从1开始编号. 然后枚举每个节点为根节点的情况（分类思想); 而当选定某个节点i 为根节点后，这个i 节点 的左右两边的节点数分别为 i -1 , n-i , 所以以这个i 为根节点的二叉树的个数为其左边节点构成的二叉树个数 * 其右边节点构成的二叉树个数, 即：f(i-1) * f(n - i).

由此就可能得到卡特兰数的递推关系，不重不漏.

• liuyubobobo #1

  赞！感谢分享：）

Answer 2

liuyubobobo 2019-02-26 01:27:21

非常抱歉，由于卡特兰数属于组合数学的经典内容，不属于数据结构的内容，不在这个课程的范畴里。课程问答区主要用于解答课程相关的问题。请谅解。

同时，不在这个课程内的问题由于缺少相应的知识体系支撑，我也不可能在问答区一句话两句话就讲明白。还请在互联网上查找相关资料或者社区进行学习交流：）

不过组合数学确实是对于计算机专业来讲非常重要的数学分分支，同时也是离散数学中非常重要的数学分支。有机会我会考虑单独开课的：）

加油！：）

• triump #1

  其实就是一个组合数学里最基本的乘法原理(分步)与加法原理（分类）的一个复合.
  设f(n) 为n 个节点所构成的不同结构二叉树的总数. 
  则 f(n) = f(0)*f(n-1) + f(1)*f(n-2)+ f(2)*f(n-3) + .........f(n-1) * f(0)
  其中f(0) = 1.
  这个就是卡特兰数的递推关系.