打印树中的所有路径(不仅仅是根到节点)
打印树中的所有路径(不仅仅是根到节点)
提问于 2015-01-18 02:31:58
那么如何打印树中的所有路径呢？这里的条件是，我们不希望路径只从根或子树中的路径开始。
例如：
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(n^3)。有没有更有效的解决方案？
回答 2
Stack Overflow用户
发布于 2015-01-18 03:05:12
如果您只对结果感兴趣，而对算法不感兴趣，请使用以下命令在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)Stack Overflow用户
发布于 2015-01-18 21:56:02
假设你的树有不同的节点，你可以：
- 创建一个映射，将键作为整数，值作为向量。键代表你遇到的每一个节点，向量是用来存储你要遍历的节点下的所有节点。
- 将这个映射按值传递给每个节点。您可以使用如下函数：
void proot(printAllPaths* map>m)
- 每当您遇到新节点n时，请执行以下操作
a)对于密钥集合中的每个k
b)将n加到k的值向量上。
c)打印所有键，后跟它们的值向量。
d)将新的键作为n插入到映射中，并将空向量作为值。
注意:如果您的树有重复的节点，则多重映射将帮助您跟踪。在这种情况下，c++ STL将很好地为您服务。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/28002850
复制相关文章
相似问题
腾讯云开发者
