通用树的节点之间的距离

Question

已知子节点到父节点的距离，求通用树的任意节点之间的距离？
有思路吗？

Answer 1

该回答引用ChatGPT

可以使用递归的方式求解通用树的任意节点之间的距离。假设给定一棵通用树，其中每个节点都存储了指向其父节点的指针，以及其子节点的指针数组。

对于任意一对节点 u 和 v，它们之间的距离可以表示为 u 到它们的最近公共祖先节点 w 的距离加上 v 到 w 的距离。因此，我们可以先找到 u 和 v 的最近公共祖先节点 w，然后计算出它们之间的距离。

如何找到 u 和 v 的最近公共祖先节点 w 呢？可以使用递归的方式从根节点开始查找。具体来说，假设当前节点为 p，我们在它的子节点中查找是否包含 u 和 v，如果分别在不同的子节点中找到了 u 和 v，则 p 就是它们的最近公共祖先节点 w。否则，我们在包含 u 和 v 的子节点中递归查找 w。

下面是一个示例代码，假设我们已经实现了一个节点类 Node，其中 parent 指向父节点，children 指向子节点的指针数组，dist 指向父节点的距离：

class Node:
    def __init__(self, parent=None, children=None, dist=0):
        self.parent = parent
        self.children = children if children else []
        self.dist = dist

def lca(u, v):
    # 如果 u 或 v 是根节点，直接返回根节点
    if not u.parent or not v.parent:
        return u.parent or v.parent

    # 如果 u 和 v 相等，直接返回 u
    if u == v:
        return u

    # 在 u 和 v 的子节点中查找是否包含 u 和 v
    u_found = False
    v_found = False
    for child in u.parent.children:
        if child == u:
            u_found = True
        elif child == v:
            v_found = True

        if u_found and v_found:
            # 如果分别在不同的子节点中找到了 u 和 v，则当前节点是它们的最近公共祖先节点
            return u.parent

    # 在包含 u 和 v 的子节点中递归查找
    for child in u.parent.children:
        if child != u:
            w = lca(child, v)
            if w:
                return w

    return None

def distance(u, v):
    # 找到 u 和 v 的最近公共祖先节点
    w = lca(u, v)

    # 计算 u 到 w 的距离和 v 到 w 的距离
    d1 = 0
    while u != w:
        d1 += u.dist
        u = u.parent

    d2 = 0
    while v != w:
        d2 += v.dist
        v = v.parent

    return d1 + d2