我正在解決一個演算法問題：
給你一棵二叉樹
root。在一項操作中，您可以洗掉樹中的一個葉節點。回傳洗掉整棵樹的不同方式的數量。所以，如果樹是：
1
/ \
2 3
/
4
預期的答案是3：[2, 4, 3, 1]和。[4, 2, 3, 1][4, 3, 2, 1]
我一直在努力思考，但我不知道如何制定遞回函式。沿著我們計算“你可以爬到頂部的不同方式”的爬樓梯問題的思路思考，我認為我必須使用 DP，但我無法制定遞回關系。
如果您能提供一些提示/指導，我將不勝感激。謝謝！
編輯：給定以下樹：
1
/ \
2 3
/ \
4 5
有兩種方法可以洗掉3( 4, 5) 的孩子；但是如何使用這些資訊來確定根節點的方式數量1？（預期的答案是8）。
uj5u.com熱心網友回復：
對于給定節點X，我們想知道u(X)- 唯一洗掉序列的數量。
假設該節點有兩個子節點A，B大小|A|為 ，|B|已知u(A)和u(B)。
您可以構建多少個洗掉序列X？您可以從u(A)andu(B)和 root 中獲取任意兩個序列并將它們組合在一起。如果滿足以下條件，結果將是一個有效的洗掉序列X：
X必須最后洗掉根。- 從不同子樹中洗掉任意兩個節點的順序是任意的。
- 給定其選擇的洗掉順序，從同一子樹中洗掉任意兩個節點的順序是固定的。
這意味著您想找出可以交錯兩個序列（和 append X）的方法的數量。
請注意，洗掉序列的長度是樹的大小，如果您考慮一下，這有點微不足道。
還要考慮這樣一個事實，即我們可以通過這種方式生成 的所有洗掉序列X，這可能不是那么簡單。
因此，如果我計算正確，您正在尋找的公式是u(X)= [|A| |B| choose |A|] * u(A) * u(B).
如果我們定義，它也適用于空孩子u(empty)=1。
只是要小心溢位，組合的數量會很快爆炸。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/426855.html