如何找到一棵樹的最低共同祖先？

Question

有沒有使用額外的空間來找到nary樹的LCA的方法。 我用一個字符串保存了這兩個節點的前序並找到了公共前綴

Answer 1

如果節點「知道」它們的深度 - 或者您願意允許空間計算節點的深度，那麼您可以返回從較低節點到較高節點的相同深度，然後一次上升一層直到它們相遇。

取決於在這種情況下「額外空間」的含義。你可以用一個整數來完成 - 兩個節點的深度差異。那太多了嗎？

另一種可能性是您沒有父指針，您可以使用指針反轉 - 每次遍歷指針時，請記住您來自的位置，請記住您將在下一次遍歷的指針，然後在之前下一個指針遍歷，將該指針替換爲後指針。在樹上恢復時，必須將其撤消。這將一個指針的空間作爲臨時的。另一個整數可以保持深度，因爲你一直在努力工作。爲所尋找的兩個節點同步執行此操作，以便您可以從較低的那個節點繼續工作，直到兩次遍歷中的高度相同，然後從兩個節點恢復工作，直到處於共同節點。這需要三個額外的內存 - 一個用於當前深度，一個用於在指針反轉期間使用的臨時內存。非常節省空間。這值得麼？

Answer 2

對兩個節點進行同步步行。

• 從LCA = root開始;
• 循環：
• 找到步驟採取A和對於B
• 步驟，如果這些是等於{LCA =步驟; decend A;下降B;轉到循環; }
• 完成：LCA現在包含A用LCA和B

僞碼C：

struct node { 
     struct node *offspring[1234]; 
     int payload; 
     }; 

     /* compare function returning the slot in which this should be found/placed */ 
int find_index (struct node *par, struct node *this); 

struct node *lca(struct node *root, struct node *one, struct node *two) 
{ 
struct node *lca; 
int idx1,idx2; 

for (lca=root; lca; lca=lca->offspring[idx1]) { 
    idx1 = find_index(lca, one); 
    idx2 = find_index(lca, two); 
    if (idx1 != idx2 || idx1 < 0) break; 
    if (lca->offspring[idx1] == NULL) break; 
    } 
return lca; 
} 

Answer 3

回去做了一個二叉樹。如果你可以做一個二叉樹，你可以做一個n-ary樹。

這裏的a link to LCA in a binary tree：

而這裏的將其轉換爲n元樹LCA後，它的外觀：

public class LCA { 

    public static <V> Node<V> 
       lowestCommonAncestor(Node<V> argRoot, Node<V> a, Node<V> b) { 

     if (argRoot == null) { 
     return null; 
     } 

     if (argRoot.equals(a) || argRoot.equals(b)) { 
     // if at least one matched, no need to continue 
     // this is the LCA for this root 
     return argRoot; 
     } 

     Iterator<Node<V>> it = argRoot.childIterator(); 
     // nr of branches that a or b are on, 
     // could be max 2 (considering unique nodes) 
     int i = 0; 
     Node<V> lastFoundLCA = null; 
     while (it.hasNext()) { 
     Node<V> node = lowestCommonAncestor(it.next(), a, b); 
     if (node != null) { 
      lastFoundLCA = node; 
      i++ ; 
     } 
     if (i >= 2) { 
      return argRoot; 
     } 
     } 

     return lastFoundLCA; 
    } 

    }