algorithm - 使用标签重新排列树

Question

考虑一棵树(无序)，其中节点标记为 0 到 n，根节点始终标记为 0。

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

例如，给定这棵树:

所需的输出是:

注意节点 2 的标签比它的父节点 5 小，所以它向上移动了树；节点 4 小于它的父节点 7 和它的祖父节点 5，所以它向上移动树到它的曾祖父节点 0。

天真的方法是独立处理每个节点，向上遍历直到我们遇到较低的标签。对于以下情况，这变得非常昂贵:

感觉应该有一个相当简单的次二次算法来处理这样的重排，但我无法制定正确的混合物，甚至找不到明显的遍历顺序来最小化冗余处理量。这是定义明确的解决方案的常见问题吗？

Answer 1

算法如下:

1. 设0为一棵树的根
2. 对原始树执行 DFS。
3. 执行递归注入(inject)。

递归注入(inject)(节点，父节点):

1. 如果节点大于父节点，则作为父节点的子节点注入(inject)。
2. 否则递归注入(inject)(节点，parent.parent)