使用标签重新排列树

Question

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

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

例如，给定这棵树：

要求的输出是：

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

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

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

Answer 1

算法如下：

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

递归注入（节点，父节点）：

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