0

这是我提出的用于非递归查找二叉树中两个节点的最低共同祖先的算法。以下是基本策略：

  1. 使用字典/哈希表来存储树。每个键值对代表一个节点及其父节点。
  2. 从两个节点中的每一个开始，通过将表示每个节点的值的变量设置为其父节点的值，将遍历的值存储在一个哈希集中（两个节点中的每一个节点一个），从而向上遍历树。
  3. 当满足以下任一条件时，搜索完成： (a) 两个节点的值相等；或 (b) 当两条路径相互交叉时（即节点 1 的遍历值的哈希集包含节点 2 的当前值，反之亦然）；或 (c) 传入的节点在树中不存在（在这种情况下，算法终止并返回 -1）。

我的理解是，我的算法的最坏情况时间和空间复杂度是 O(log(n))，因为我们永远不需要进行超过 2 * 高度遍历或在哈希集中存储超过 2 * 高度值（并且因为哈希集和树字典的查找时间为 O(1))。

以下是我的代码（C#）。请告知我的分析是否正确，或者是否有更有效（非递归）的方法来执行此操作：

int LowestCommonAncestor(int value1, int value2, Dictionary<int, int> tree)
{
    var value1Visited = new HashSet<int>();
    var value2Visited = new HashSet<int>();
    while (true)
    {
        if (value1 == value2) return value1;
        if (value1Visited.Contains(value2)) return value2;
        if (value2Visited.Contains(value1)) return value1;

        int nextValue1;
        int nextValue2;

        if (tree.TryGetValue(value1, out nextValue1))
        {
            //Walk node 1 up the tree:
            value1 = nextValue1;
            value1Visited.Add(value1);
        }
        else
        {
            //Node doesn't exist in tree:
            return -1;
        }

        if (tree.TryGetValue(value2, out nextValue2))
        {
            //Walk node 2 up the tree:
            value2 = nextValue2;
            value2Visited.Add(value2);
        }
        else
        {
            //Node doesn't exist in tree:
            return -1;
        }
    }
}
4

3 回答 3

0

  1. 从每个节点向上到根以测量其深度

  2. 从较深的节点向上移动路径，直到到达与较浅节点相同的深度。

  3. 从两个节点向上移动路径（即，在两个路径上保持相同的深度）直到它们相遇。

于 2017-01-01T21:58:47.793 回答
0

那么，这是我修改后的算法：

int LCA(int value1, int value2, Dictionary<int, int> tree)
{
    if (!tree.ContainsKey(value1) || !(tree.ContainsKey(value2))) return -1;

    int depth1 = 0;
    int depth2 = 0;
    int tmpVal1 = value1;
    int tmpVal2 = value2;

    while (tmpVal1 != -1)
    {
        tmpVal1 = tree[tmpVal1];
        depth1++;
    }

    while (tmpVal2 != -1)
    {
        tmpVal2 = tree[tmpVal2];
        depth2++;
    }

    if (depth1 > depth2)
    {
        while (depth1 > depth2)
        {
            value1 = tree[value1];
            depth1--;
        }
    }

    else if (depth2 > depth1)
    {
        while (depth2 > depth1)
        {
            value2 = tree[value2];
            depth2--;
        }
    }
    while (value1 != value2)
    {
        value1 = tree[value1];
        value2 = tree[value2];
    }

    return value1;
}
于 2017-01-02T06:33:24.167 回答
0

您不需要两个哈希集。

  1. 向上并在单个哈希集中收集一个节点的祖先
  2. 从第二个节点向上，并在其每个祖先处，检查在步骤 1 收集的路径是否包含第二个节点的当前祖先。停在第一个常见的地方。

D 是树的最大深度，复杂度是 O(D) 最坏情况复杂度。

N 中的最坏情况复杂度 - 节点数 - 当树在列表中退化时，其中一个节点是该列表的头部，另一个是尾部。

如果树是平衡的，则 D=log(N) - log 的基数是节点的后代数（二进制 - log2，三进制 - log3 等）。

于 2017-01-01T22:28:48.607 回答