是否可以找到没有最低公共祖先（或从根开始的路径）的通用树的两个节点之间的距离

Question

对于二叉树，可以找到两个节点之间的距离，而无需找到从根节点或最低公共祖先开始的路径。我想知道在通用树的情况下是否可能。因为在通用中找到最低共同祖先是可能的，如下面的代码所示。

TreeNode* findLCA(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* lca = nullptr;
    int count = 0;

    for (auto child : root->children) {
        TreeNode* node = findLCA(child, p, q);
        if (node) {
            count++;
            lca = node;
        }
        if (count == 2) return root;
    }

    return lca;
}

有人可以帮我理解我做错了什么，或者建议一个更好的方法来解决这个问题而不找到 LCA 吗？任何帮助将不胜感激！

Answer 1

树上的统一成本搜索（UCS）寻路

如果你的树是通用的，不一定是二元的，那么你最终处理的是一个连接的森林，因此，是一个非循环图（特别是不一定有向的图）。因此，您可以通过将 p 或 q 设置为起始/结束节点来简单地进行 统一成本搜索（

Dijkstra 算法的

封闭域

变体

）。

UCS 的工作原理与 Dijkstra 算法类似，但强烈要求定位称为“目标状态”的特定节点。当找到所有目标状态时，算法将停止（并可选择报告遍历的路径）。这里的挑战是树是未加权的，因此必须平等对待所有边，从而在处理边时引入一些自定义。在最坏的情况下，我们探索图中的所有边和节点，而不需要任何昂贵的重复工作（如果仔细实现），并且由于我们平等地对待所有边，因此不需要用于优先考虑最低成本的二进制堆，因此线性时间执行可以代替对数线性（或“线性算术”）运行时来实现。此外，现在隐含了“成本”的概念，并且不再相关 - 它只是我们希望模仿的 UCS 的

行为

。 伪代码

以下是如何在被视为连通森林和无向无环图的树上执行修改后的 UCS 算法的细分和伪代码。

强烈建议此时熟悉UCS的内部运作

，教授已经有一个

精彩的解释

。约翰·莱文。我将使用类似于 Active-Records Design Pattern 的设计模式来构建用于跟踪路径的优先级表。

算法：在树中查找路径

初始化一个包含起始状态p

的队列，并初始记录树/图中所有节点的默认状态；抢先将

p

标记为已访问以启动执行；

V(G)

是树中所有节点（顶点）集合的图论符号约定：

queue ← deque([p])
path_table(v) ← Record(predecessor ← None, visited ← False) for all v in V(G)
path_table(p).visited ← True

While 循环搜索目标状态

:

While queue is not empty:
    current_node ← queue.pop_left()
    If current_node equals q:
        Break loop (Goal found)

    For each edge e incident to current_node:
        child ← e.opposite(current_node)
        If path_table(child).visited equals False:
            path_table(child).visited ← True
            path_table(child).predecessor ← current_node
            queue.append(child)

路径重建：

Initialize empty list path_list
current_node ← q
While current_node is not None:
    path_list.append(current_node)
    current_node ← path_table(current_node).predecessor

返回结果：

Return (path_table, reverse(path_list))

实施

我已经在 Python here 中实现了这个算法，利用邻接图 ADT 来表示我的非循环、连通、树状图；但是，由于某些依赖结构，您可能必须克隆整个存储库才能运行代码（您需要使用 PyCharm）；这种冗长正是我选择不在此包含代码的确切原因，因为它无法正确插入。因此，让我们探讨两个示例，展示链接实现的确切输出。

示例1：传统二叉树

S / \ A B / C / \ D G1 / E / \ F G2 \ G3 假设我们从节点

p = A

 开始，我们想要找到一条到节点

E

的路径，

Find Path in Tree

算法会返回距离记录，告诉您在遇到目标状态后停止时访问了哪些节点

 q = E

：

START :: -> A -> S -> B -> C -> D -> E -> END

Node | Pred | Visited   |
S    |  A   |   True    |
A    |  $   |   True    |
B    |  S   |   True    |
C    |  B   |   True    |
D    |  C   |   True    |
E    |  D   |   True    |
F    |  $   |   False   |
G1   |  C   |   True    |
G2   |  $   |   False   |
G3   |  $   |   False   |

注意算法如何隐式地将

A

 视为根，将其前驱标记为终端 (

$

)/空节点，同时将其标记为已访问？这类似于 BFS、DFS 或 Dijkstra 执行的遍历分别称为 BFS 树、DFS 树和 Dijkstra 树，因为每次遍历都会返回以起始节点为根的树。但是，请注意，未访问的节点（在访问的列下标记为 false）也将终止字符串作为其前任。主要区别在于根始终标记为已访问。

为了充分披露，这是当您从节点

开始并选择

G3

作为目标状态时的结果：

你能猜出距离记录中发生了什么吗？

所有节点都被访问！

START :: -> S -> B -> C -> D -> E -> F -> G3 -> END Node | Pred | Visited | S | $ | True | A | S | True | B | S | True | C | B | True | D | C | True | E | D | True | F | E | True | G1 | C | True | G2 | E | True | G3 | F | True |

示例 2：通用非二叉树

S / | \ A B C / \ / | \ D E F G H | | I J / \ / K L M 与之前一样，设置

p = K

和

q = F

会产生以下结果：

START :: -> K -> I -> E -> A -> S -> C -> F -> END

Node | Pred | Visited   |
S    |  A   |   True    |
A    |  E   |   True    |
B    |  S   |   True    |
C    |  S   |   True    |
D    |  A   |   True    |
E    |  I   |   True    |
F    |  C   |   True    |
G    |  C   |   True    |
H    |  C   |   True    |
I    |  K   |   True    |
J    |  $   |   False   |
K    |  $   |   True    |
L    |  I   |   True    |
M    |  $   |   False   |

是否可以找到没有最低公共祖先（或从根开始的路径）的通用树的两个节点之间的距离

问题描述投票：0回答：1

1个回答

树上的统一成本搜索（UCS）寻路

，教授已经有一个

最新问题

是否可以找到没有最低公共祖先（或从根开始的路径）的通用树的两个节点之间的距离

问题描述 投票：0回答：1

1个回答

树上的统一成本搜索（UCS）寻路

，教授已经有一个

最新问题

问题描述投票：0回答：1