<分区>
我们有一棵树，在给定的第 2 级节点上有尽可能多的 child ，我们必须找到两个节点之间的路径，我们该怎么做？
1
/ | \
2 3 4
/ \ | / \
5 8 11 12 13
/\ |
6 9 14
/ \
7 10
我们必须找到节点 7 和 14 之间的路径。结果应该是:
7 -> 6 -> 5 -> 2 -> 1 -> 4 -> 12 -> 14
最佳答案
假设我们想要找到节点 A 和 B 之间的路径。
一种简单的方法是找到两个节点的最低共同祖先 (LCA)。蛮力方法是找到从根到 A 以及从根到 B 的路径(您可以使用广度优先或深度优先遍历来做到这一点)并将路径存储在列表中。遍历列表以查看最低的公共(public)节点，如果没有，它将是根本身。现在您有两条从节点 A 到 LCA 和从节点 B 到 LCA 的部分路径，连接这些路径以获得从 A 到 B 的路径。
如果树提供更多功能，如父指针或每个节点的级别数等，则可以更有效地完成。例如，如果存在父指针，您可以从单个节点开始向上移动到根节点，并在它们到达公共(public)节点时停止。
关于c - 一棵树在任何级别都有多个 child ，找到两个节点之间的路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18689199/