打印树中的所有路径（不仅仅是根到节点）

Question

那么，如何打印树中的所有路径呢。这里的条件是，我们不仅需要从根开始的路径或子树中的路径。

例如：

     2
    / \
   8   10
  /\   /
 5  6 11

因此程序应该返回：

2-8
2-10
2-8-5
2-8-6
8-5
8-6
2-10-11
10-11
5-8-2-10-11
5-8-2-10
and so on...

一种方法是在每个不同的节点对之间找到LCA，然后打印从LCA到两个节点的路径（在左子树中反转，在右子树中按顺序排列）。但是这里的复杂性是O（n3）。有更有效的解决方案吗？

Answer 1

假设树具有不同的节点，则可以：

按值将此映射传递给每个节点。您可以有一个函数，例如：

void printAllPaths(node *proot, map<int, vector<int> > m)

每当您遇到新的节点n时，请执行以下操作

a） 对于密钥集中的每个k

b） 将n添加到k的值向量。

c）打印所有键及其值向量。

d）还将新键作为n插入到以空向量作为值的映射中。

注意：如果你的树有重复的节点，多重映射将帮助你跟踪。在这种情况下，c STL将很好地为您服务。

Answer 2

如果您只对结果感兴趣，而对算法不感兴趣，请使用以下命令在neo4j中创建节点和关系：

merge (n2:node{n:2})-[:down]->(n8:node{n:8})-[:down]->(:node{n:5})
merge (n2)-[:down]->(:node{n:10})-[:down]->(:node{n:11})
merge (n8)-[:down]->(:node{n:6})

然后查询

match p=(a)-[r:down *]-(b) return nodes(p)