在任何级别具有多个子节点的树,找到两个节点之间的路径

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)。强力方法是找到从 root 到 A 以及从 root 到 B 的路径（您可以使用广度优先或深度优先遍历来做到这一点）并将路径存储在列表中。遍历列表以查看最低的公共节点，如果没有，则它就是根本身。现在您有从节点 A 到 LCA 和从节点 B 到 LCA 的两条部分路径，连接这些路径即可获得从 A 到 B 的路径。

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