首页 > 试题广场 > 对于一棵二叉树,独立集是指两两互不相邻的节点构成的集合。例如
[填空题]
对于一棵二叉树,独立集是指两两互不相邻的节点构成的集合。例如,图 1 有 5 个不同的独立集(1 个双点集合、3 个单点集合、1 个空集),图 2 有 14 个不同的独立集。那么,图 3 有___1______个不同的独立集。

初赛题要手动。。我傻了都。。

​设表示以的子树中独立集个数,表示选择节点,表示不选节点。

​独立集中的点两两不相邻,所以扩展时不能选两个子节点,扩展时直接左右儿子答案相乘(计数原理)即可。

​则得到递推式:

​按后序遍历编号,求出即可。

发表于 2019-10-13 22:15:48 回复(0)