最快的非遞歸實施LCA？

Question

這是我提出的非遞歸尋找二叉樹中兩個節點的最低公共祖先的算法。這裏的基本策略：

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; 
     } 
    } 
} 

Answer 1

1. 從每個節點進入到根來衡量其深度

2. 向上移動從較深節點開始的路徑，直到深度與較淺節點相同。

3. 上移兩個節點的路徑（即保持兩條路徑上的深度相同），直到它們相遇。

Answer 2

您不需要兩個散列集。

1. 上去，並在單個散列收集設置一個節點的祖先
2. 從第二節點上去，在其每個祖先的，檢查是否在步驟1中收集的路徑包含的當前祖先第二。在第一個常見的站點停下來。

隨着D是樹的最大深度，複雜度是O（D）最壞情況下的複雜度。

在N-最壞的情況複雜 - 節點的數量 - 在樹列表中的簡併，該節點是該列表的頭部與其他的一個是尾。

如果樹是平衡的，d =日誌（N） - 與日誌的基礎是一個節點的後代的數量（二進制 - LOG2，三元 - log3中，等等）。

Answer 3

那麼，這裏是我的修訂後的算法：

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; 
}