树中所有边缘不相交路径的列表

Question

在由具有父指针和子指针的公共节点结构表示的通用树中,如何找到彼此没有重叠边缘并且以叶节点终止的所有路径的列表.

例如,给定一个这样的树:

          1
      /   |   \               
     2    3    4
    / \   |   / \
   5   6  7  8   9 

所需的输出将是一个路径列表,如下所示:

1    2    1    1    4
|    |    |    |    |
2    6    3    4    9
|         |    | 
5         7    8

或者以列表形式:

[[1, 2, 5], [2, 6], [1, 3, 7], [1, 4, 8], [4, 9]]

显然,路径列表本身及其顺序可以根据树枝的处理顺序而变化.例如,如果我们首先处理左分支,则以下是另一种可能的解决方案:

[[1, 4, 9], [4, 8], [1, 3, 7], [1, 2, 6], [2, 5]]

为了这个问题,不需要特定的订单.

Answer 1

对于所有顶点，如果该顶点是叶子（没有子指针），则遍历父链，直到找到标记的顶点或没有父节点的顶点。标记所有访问过的顶点。将顶点收集到中间列表，然后将其反转并添加到结果中。

如果无法向顶点对象本身添加标记，则可以将标记实现为一组单独的已访问顶点，并将添加到该集合的所有顶点视为已标记。