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

初赛题要手动。。我傻了都。。
设表示以
的子树中独立集个数,
表示选择
节点,
表示不选
节点。
独立集中的点两两不相邻,所以扩展时不能选两个子节点,
扩展时直接左右儿子答案相乘(计数原理)即可。
则得到递推式:,
。
按后序遍历编号,求出即可。