重新排列用树标签

Question

考虑一个树（无序的），其中所述节点通过n个标记为0，与始终标记为0

我希望构造一个单独的树，根节点，其中，每个非父 - 根节点m是其最近的祖先，标签小于m。

例如，给定此树：

所需的输出是：

注意，节点2具有比其父5在较小的标签，所以其移动在树上;节点4比它的父亲7和它的祖父母5少，因此它向上移动到它的祖辈0。

幼稚的方法是独立处理每个节点，遍历向上，直到遇到较低的标签。这将成为如情况非常昂贵：

感觉就像应该有处理这种重新安排一个相当简单的子二次算法，但我不能制定正确的药汁，甚至找到一个明显的遍历顺序可以最大限度地减少冗余处理的数量。这是一个定义明确的解决方案的常见问题吗？

Answer 1

该算法将是以下：

1. 设定0作为树的根
2. 原始树执行DFS。
3. 执行递归注入。

递归注入（节点，父）：

1. 如果节点比亲本大，注入作为母体的孩子。
2. 否则递归注入（node，parent.parent）