一个具有3个节点的二叉树可以有()种形态。_网易互娱笔试题

推荐

牛客-007

答案：5

这里将三个节点分别表示为A，B，C。（ABC等价，不做区分），假设A为 root

第一种情况：B是A的左孩子，C是A的右孩子

第二种情况：B是A的左孩子，C是B的左孩子

第三种情况：B是A的左孩子，C是B的右孩子

第四种情况：B是A的右孩子，C是B的右孩子

第五种情况：B是A的右孩子，C是B的左孩子

编辑于 2015-02-02 11:24:18 回复(0)

王俊超

答案：5

求卡特兰数：h(n)=C(n, 2n)/(n+1)，代入3解得h(3)=5

发表于 2015-08-03 16:32:21 回复(0)

Jemmy

Catalan数

发表于 2016-08-17 22:35:05 回复(0)

拒绝2015

可以把非线性的树问题看成栈的问题，3个数进入栈，出来的结果又五种情况，所以5.

发表于 2015-10-13 15:47:32 回复(1)

半城烟沙！

发表于 2015-11-15 22:42:18 回复(0)

舒意意123

又学到一些知识

发表于 2017-03-16 15:07:19 回复(0)

Sai0514

学习新公式，m=C(n,2n) /(n+1)

发表于 2017-03-02 09:27:04 回复(0)

keyu88888

记n个节点的二叉树形态个数为A[n]

1）0个节点的二叉树只有1种形态，A[0]=0；1个节点的二叉树只有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数，直接用catalan数的公式：h(n)=C(2n,n)/(n+1)

发表于 2016-10-24 15:01:30 回复(0)

bleedgreen

5种

发表于 2015-09-11 15:56:35 回复(0)

若水/爆米花

设具有N个节点的二叉树的形态有f(N)种,则f(0)=0,f(1)=1
具有3个节点的二叉树,包含一个根节点与2个子节点,可以分以下几类：
左子树0个节点,右子树2个节点,此时二叉树的形态有f(0)+f(2)
左子树1个节点,右子树1个节点,此时二叉树的形态有f(1)
左子树2个节点,右子树0个节点,此时二叉树的形态有f(2)+f(0)
故f(4)=2f(0)+f(1)+2f(2)
f(2)=2f(0)+2f(1)=2
所以f(4)=5,即具有3个节点的二叉树有5种.

发表于 2015-08-11 10:23:13 回复(0)

Duane

4

发表于 2015-05-24 00:27:12 回复(1)

一个具有3个节点的二叉树可以有()种形态。

问题信息

热门推荐

相关试题