一棵树,每个节点有0或2个孩子,共N个节点,高度为K,问可以组成多少种不同的结构?
假设,当前树的节点问n,高度为k,那么子树可分为3种情况:
- 左子树高度为k-1,右子树高度为1~k-2
- 右子树高度为k-1,左子树高度为1~k-2
- 左右子树均为k-1
并且,满足题目要求的树的节点与高度有这样的关系:2*k-1 <= n <= 2^k-1,可是根据这个关系枚举左右子树的节点数
于是就可以用递归+DP的方法解出这道题了。
(在对n <= 2^k-1进行转化时,自己居然写成了k >= log(n+1.0)/log(2.0),其实应该是k >= floor (log(n+1.0)/log(2.0)),还是太粗心啦)