一棵樹,每個節點有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)),還是太粗心啦)