algorithm - 树 : Find node whose common path is shortest in relation to other nodes

Question

A|'-- B    |    '-- C    |   |    |   '-- X1    |    '-- D        |        '-- E        |   |        |   '-- F        |       |        |       '-- X2        |        '-- X3

给定一棵树和到该树内节点的多条路径，我如何设计一种算法来返回树内与其他节点具有最少公共(public)路径的节点。

例如:

我们有以下到 x 的路径:

1. A -> B -> C -> x1
2. A -> B -> D -> E -> F -> x2
3. A -> B -> D -> x3

我们可以看到 x2 和 x3 共享一条公共(public)路径:A -> B -> D 比共享路径长通过 x1 和 x2 (A -> B) 或者 x1 和 x3< 共享的路径 (A -> B).

我的目标是通过算法找到 x1。

Answer 1

观察:从根向下到每个叶子，公共(public)路径将从根到它们最低的公共(public)祖先节点。在这个例子中，最低共同祖先是节点 B 和节点 D。因此，这个问题的结果将始终在从根到最近的最低共同祖先的路径中。

另请注意，从一个最低公共(public)祖先节点向下一层，我们将始终有一条路径不包含任何其他最低公共(public)祖先节点。

所以我会提出一个解决方案，它需要在树中进行两次遍历。

对于树中的每个节点，我们记录了一个额外的信息，整数count，它将告诉在这个节点，它的叶子中包含多少个X对象(即X1，X2，X3在示例中)。

class Node {
   int count = 0;
   Node []children;
}

因此，通过一次传递，我们可以更新所有count 信息。

public int getCount(Node node){
    if(children is empty){
       if(this node contains object in the list)
          return 1;
       return 0;
    }else{
       for(Node child in children){
           node.count += getCount(child);
       }
    }
    return node.count;
}

在第二遍中，从根向下到每个叶，问题的结果在具有 count == 1 且最接近根的节点中。 最近的根实际上是树中节点的级别。

所以，在这个例子中，每个节点的计数是:

A:3(0级)

B:3(1 级)

C : 1(级别 2)包含最接近根的结果

D:2(2 级)

E:1(3 级)

F : 1(4 级)

所以，最后，时间复杂度是 O(N)，其中 N 是节点数。

注意:正如 NiklasB 所提到的，整个过程可以一次完成。

只需修改 getCount 方法以包括到 root 的距离，以及两个全局变量，min 保持具有计数的节点的最小距离是1、另一个持有对象result。

int min = 100000;
Object result;

public int getCount(Node node, int distance){
    if(children is empty){
       if(this node contains object in the list)
          if(distance < min){ 
             min = distance;
             result = //X 
          }
          return 1;
       return 0;
    }else{
       for(Node child in children){
           node.count += getCount(child , distance + 1);
       }
    }
    if(node.count == 1 && distance < min){
       min = distance,
       result = //X
    }
    return node.count;
}