algorithm - 具有重复值的大型二叉树中两个值之间的最小距离

Question

给定一个可能包含重复值的二叉树，您需要找到两个给定值之间的最小距离。请注意，二叉树可能很大。

例如:

        5
      /   \
    1       7
   / \     / \
  4   3   8   2
 / \
1   2

该函数应为(1 和 2 作为输入)返回 2。
(如果不存在重复项，我们可以找到 LCA，然后计算距离。)

我已经编写了以下代码，但我无法处理值出现在不同子树中的情况以及以下情况:

1. root = 1, root.left = 4, root.left.left = 3, root.left.right = 2, root.left.left.left = 1
2. root = 1, root.left = 4, root.left.left = 3, root.left.left.left = 1, root.left.left.right = 2

void dist(struct node* root,int& min,int n1,int n2,int pos1,int pos2,int level) {
    if(!root)
        return;
    if(root->data==n1){
        pos1 = level;
        if(pos2>=0)
            if(pos1-pos2 < min)
                min = pos1-pos2;
    }
    else if(root->data==n2){
        pos2 = level;
        if(pos1>=0)
            if(pos2-pos1 < min)
                min = pos2-pos1;
    }
    dist(root->left,min,n1,n2,pos1,pos2,level+1);
    dist(root->right,min,n1,n2,pos1,pos2,level+1);
}

我认为在每个节点我们都可以找到该节点是否是值的 LCA。如果该节点是 LCA，则找到距离并相应地更新最小值，但这需要 O(n²)。

Answer 1

以下是解决问题的算法:-

遍历所有树并使用二进制字符串表示计算每个节点的路径并存储到 HashMap 中

例如。对于你的树， HashMap 将是

1 => 0,000
2 => 001,11
3 => 01
...

当查询 (u,v) 之间的距离时，检查每一对并计算它们之间的距离。从字符串中删除公共(public)前缀，然后对剩余长度求和

eg. u=1 and v=2

distance(0,001) = 2
distance(0,11) = 3
distance(000,001) = 2
distance(000,11) = 5 

min = 2

注意:我认为第二步可以更高效，但需要做更多研究