選擇包含完全K葉的子樹

Question

我給了一棵樹T其中有n節點和l樹葉。

我不得不選擇一些包含k (<=l)葉子的子樹。如果我選擇節點t的祖先子樹，我們不能選擇t的子樹。

例如：

這是有13個節點（7個葉）樹T。

如果我想選擇k = 4樹葉，我可以選擇節點4和6（或節點2和5）。這是選擇的最小數量。 （我們可以選擇節點6,7,8,9，但這不是最小值）。

如果我想選擇k = 5樹葉，我可以選擇節點3，這是選擇的最小數量。

我想選擇最小數量的子樹。我只能找到O(nk^2)和O(nk)算法，它使用BFS和動態編程。選擇這個有沒有更好的解決方案？

謝謝:)

Answer 1

其實，要知道一旦所以複雜性應該是O(nm)其中m是每個節點的孩子的平均數量每個你只需要通過每個節點子樹的葉片數，在大多數情況下，它的計算結果爲O(n)，因爲m只是一個常數。要做到這一點，你應該：

• 查找，你的樹的節點是葉
• 去了樹，節省爲每個節點葉數在其子樹

你可以這樣做通過從葉子開始並將父母放入隊列中。當您將節點n_i從隊列中彈出時，將從每個n_i的孩子開始的每個子樹中包含的樹葉數相加。一旦你完成，標誌着n_i所訪問（這樣你就不會訪問它多次，因爲它可以每一次孩子被添加）

這給了這樣的事情：

^ 
|    f (3)    This node last 
|   /\ 
|   / \ 
|  /  \ 
|  /   \ 
|  d (2)   e (1)  These nodes second 
| /\   /
| / \  /
| a (1) b (1) c (1)   These nodes first 

具體的步驟是：

Find leaves `a`, `b` and `c`. 
For each leave, add parent to queue # queue q = (d, d, e) 

Pop d         # queue q = (d, e) 
Count leaves in subtree: d.leaves = a.leaves + b.leaves 
Mark d as visited 
Add parent to queue     # queue q = (d, e, f) 

Pop d         # queue q = (e, f) 
d is visited, do nothing 

Pop e         # queue q = (f) 
Count leaves in subtree: e.leaves = c.leaves 
Mark d as visited 
Add parent to tree     # queue q = (f, f) 

Pop f         # queue q = (f) 
Count leaves in subtree: f.leaves = d.leaves + e.leaves 
Mark d as visited 
Add parent to tree (none) 

Pop f         # queue q =() 
f is visited, do nothing 

您還可以使用智能數據結構，該智能數據結構將忽略添加兩次的節點。請注意，您不能使用有序集合，因爲在「較高」節點之前探索「較低」節點非常重要。

在你的情況下，如果你的隊列中有多於k葉節點，你可以消除你隊列中的節點，並且返回你找到的葉節點，這將提供更快的算法。