graph - 查找树中两个节点之间的深度差异，而不是一直到根

Question

我遇到了一个我无法弄清楚的问题。

假设一棵二叉树，其中每个节点都有一个指向其父节点的指针和两个子节点。我们接收 r、p、q（根和树中的两个节点）的输入，我们想要找到 p 和 q 之间的深度差，而不需要一直遍历到根。

限制和假设：

• 没有内存使用（意味着没有数组，变量都可以）
• 假设节点 Lowest Common Ancestor 不是根（为了简单起见，我们假设 LCA 远离 Big-O 表示法中的根。

只是为了澄清 - 基本上，问题是我们如何在不一直到根部且没有记忆的情况下找出深度差异。

谢谢！

Answer 1

基本上，问题是我们如何在不一直到根部的情况下找出深度差异......

这并不是说你不能一直遍历到根。它只是说最终的结果可能不是根源。

首先，定义一个函数来确定一个节点的深度（伪代码）：

function depthOf(r, p):
    depth = 0
    temp = p
    while curr is not r:
        depth++
        temp = temp.parent
    return depth

只需为两个节点调用此函数，然后获取差异。

作为附加功能，您可以使用此信息来查找最低共同祖先：

使用深度差从两个节点中最深的节点向上走，直到与另一个节点处于相同深度。从那时起，从两个节点串联向上走，直到从两侧到达同一个节点：

function least(r, p, q)
    diff = depthOf(r, p) - depthOf(r, q)  # The answer
    # In order to find least common ancestor, continue as follows:
    while diff > 0:  # p is deeper than q
        p = p.parent
        diff--
    while diff < 0:  # q is deeper than p
        q = q.parent
        diff++
    while p is not q:
        p = p.parent
        q = q.parent
    return p