c - 一棵树在任何级别都有多个子节点，找到两个节点之间的路径

Question

我们有一棵树，在任何级别 2 节点上都有尽可能多的子节点，我们必须找到两个节点之间的路径，我们该怎么做？

                1
      /         |        \
     2          3         4
    / \         |       /   \
   5   8       11      12    13
  /\                   |
 6  9                 14
 / \
7   10

我们必须找到节点 7 和 14 之间的路径。结果应该是：

7 -> 6 -> 5 -> 2 -> 1 -> 4 -> 12 -> 14

Answer 1

假设我们想找到节点 A 和 B 之间的路径。

一种简单的方法是找到两个节点的最低共同祖先 (LCA)。蛮力方法是找到从根到 A 以及从根到 B 的路径（您可以使用广度优先或深度优先遍历来做到这一点）并将路径存储在列表中。遍历列表以查看最低的公共节点，如果没有，它将是根本身。现在您有两条从节点 A 到 LCA 和从节点 B 到 LCA 的部分路径，连接这些路径以获得从 A 到 B 的路径。

如果树提供更多功能，例如父指针或每个节点的级别数等，则可以更有效地完成。例如，如果存在父指针，您可以从单个节点开始向上移动到根节点并在它们到达公共节点时停止。