頂點從樹上移除的算法

Question

當從樹中移除頂點及其入射邊緣時，將保留一組 子樹。編寫一個算法，給定一個包含n個頂點的樹的圖，找到一個頂點v，該頂點的移除不會留下具有多於n/2個頂點的子樹。

我已經嘗試過使用修改後的DFS方法以及橋接查找算法的問題。任何幫助將非常感激。

Answer 1

創建一個遞歸函數，該函數執行樹的post-order traversal。

該函數返回子樹的大小和頂點，或者頂點可以是全局的（在這種情況下，您只需設置它而不是返回它）。

調用根的函數。

1. 在每個子樹的子樹上調用該函數。

2. 如果其中一個調用返回了一個頂點，則返回該頂點。

3. 返回當前的頂點，如果這些條件成立：

   • 每個孩子的子樹具有小於或等於n/2頂點。

   • 子樹的子樹大小總和大於或等於(n-1)/2，即子樹'當前'小於或等於n/2節點。

4. 返回子樹的大小+ 1作爲子樹大小的總和。

運行時間：O(n)。我假設你已經有樹的大小 - n - 如果不是，你需要開始另一個遍歷來獲得這個大小（這不會影響O(n)運行時間）。