重新排列用樹標籤

Question

考慮一個樹（無序的），其中所述節點通過n個標記爲0，與始終標記爲0

我希望構造一個單獨的樹，根節點，其中，每個非父 - 根節點m是其最近的祖先，標籤小於m。

例如，給定此樹：

所需的輸出是：

注意，節點2具有比其父5在較小的標籤，所以其移動在樹上;節點4比它的父親7和它的祖父母5少，因此它向上移動到它的祖輩0。

幼稚的方法是獨立處理每個節點，遍歷向上，直到遇到較低的標籤。這將成爲如情況非常昂貴：

感覺就像應該有處理這種重新安排一個相當簡單的子二次算法，但我不能制定正確的藥汁，甚至找到一個明顯的遍歷順序可以最大限度地減少冗餘處理的數量。這是一個定義明確的解決方案的常見問題嗎？

Answer 1

該算法將是以下：

1. 設定0作爲樹的根
2. 原始樹執行DFS。
3. 執行遞歸注入。

遞歸注入（節點，父）：

1. 如果節點比親本大，注入作爲母體的孩子。
2. 否則遞歸注入（node，parent.parent）