查找二叉樹中最不常見的父親？

Question

這個問題可能有很多人問過，但它有點不同。我們有一棵二叉樹。並給你兩個節點p& q。我們必須找到最不共同的家長。但是你沒有指向根的根節點指針。爲您提供兩種內置功能：

1）BOOL same(node *p, node *q); - >如果節點相同或不相等，則返回true。

2）node* parentNode(node *c); - >返回當前節點的父節點。

如果節點c實際上是root，那麼parentNode函數會返回NULL值。 使用函數我們必須找到樹的最小公共父項。

Answer 1

假設C++：

node* leastCommonParent(node *p, node *q) 
{ 
    node *pParent = parentNode(p); 
    while(pParent != 0) 
    { 
     node *qParent = parentNode(q); 
     while(qParent != 0) 
     { 
      if (0 == same(pParent, qParent)) 
       return pParent; 
      qParent = parentNode(qParent); 
     } 
     pParent = parentNode(pParent); 
    } 
    return 0; 
} 

更新：沒有使用遞歸顯式聲明變量的版本如下。我相信它可以得到改進，並且可能永遠不會在當前形式的生產代碼中使用它。

node* qParent(node *p, node *q) 
{ 
    if (p == 0 || q == 0) 
     return 0; 
    if (same(p, q) == 0) 
     return p; 
    return qParent(p, q->parent); 
} 

node* pParent(node *p, node *q) 
{ 
    return qParent(p, q) ? qParent(p, q) : pParent(p->parent, q); 
} 

node * result = pParent(p, q); 

Answer 2

第一步：使用parentNode功能找到從根目錄的節點p的距離d1。類似地找到來自根的節點q的距離d2。 （比方說，d2弄出來OT比d1更大）

步驟2：移動更遠節點（其曾經d值是更大的）指針d2-d1朝根的步驟。

第3步：同時向指針移動指針p和q，直到它們指向同一節點並返回該節點。

基本上，它會像找到兩個鏈接列表的合併點。
檢查以下鏈接： Check if two linked lists merge. If so, where?

時間複雜度：O（N）
您的代碼將有所期待沿線：

node* LCP(node* p, node *q){ 
    int d1=0, d2=0; 
    for(node* t= p; t; t = parentNode(p), ++d1); 
    for(node* t= q; t; t = parentNode(q), ++d2); 
    if(d1>d2){ 
     swap(d1, d2); 
     swap(p, q); 
    } 
    for(int i=0; i<(d2-d1); ++i) 
     q = parentNode(q); 
    if(same(p, q)){ 
     return parentNode(p); 
    } 
    while(!same(p, q)){ 
     p = parentNode(p); 
     q = parentNode(q); 
    } 
    return p; 
}