Jak znaleźć najniższego wspólnego przodka dwóch węzłów w dowolnym drzewie binarnym?

Drzewo binarne tutaj niekoniecznie musi być drzewem wyszukiwania binarnego.
Strukturę można przyjąć jako -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

Maksymalnym rozwiązaniem, które mogłem wymyślić z przyjacielem, było coś takiego -
rozważ to drzewo binarne :

Przechodzenie wewnętrzne daje - 8, 4, 9, 2, 5, 1, 6, 3, 7

A przechodzenie po zamówieniu daje - 8, 9, 4, 5, 2, 6, 7, 3, 1

Na przykład, jeśli chcemy znaleźć wspólnego przodka węzłów 8 i 5, tworzymy listę wszystkich węzłów, które znajdują się między 8 a 5 w przechodzeniu drzewa wewnętrznego, którym w tym przypadku jest [4, 9 , 2]. Następnie sprawdzamy, który węzeł na tej liście pojawia się jako ostatni w przemierzaniu zamówienia pocztowego, czyli 2. Stąd wspólnym przodkiem dla 8 i 5 jest 2.

Złożoność tego algorytmu, jak sądzę, wynosi O (n) (O (n) dla przechodzenia w kolejności / po kolejności, pozostałe kroki to znowu O (n), ponieważ są one niczym innym jak prostymi iteracjami w tablicach). Ale jest duża szansa, że ​​to źle. :-)

Ale jest to bardzo surowe podejście i nie jestem pewien, czy w jakimś przypadku się zepsuje. Czy istnieje inne (być może bardziej optymalne) rozwiązanie tego problemu?

Nick Johnson ma rację, że algorytm złożoności czasowej O (n) jest najlepszym, co możesz zrobić, jeśli nie masz wskaźników nadrzędnych.) Aby uzyskać prostą rekurencyjną wersję tego algorytmu, zobacz kod w poście Kindinga, który działa w czasie O (n) .

Pamiętaj jednak, że jeśli węzły mają wskaźniki nadrzędne, możliwy jest ulepszony algorytm. Dla obu tych węzłów utwórz listę zawierającą ścieżkę od korzenia do węzła, zaczynając od węzła i wstawiając z przodu rodzica.

Zatem dla 8 w Twoim przykładzie otrzymujesz (pokazując kroki): {4}, {2, 4}, {1, 2, 4}

Zrób to samo dla drugiego węzła, którego dotyczy problem, co spowoduje (kroki niepokazane): {1, 2}

Teraz porównaj dwie listy, które zrobiłeś, szukając pierwszego elementu, w którym lista się różni, lub ostatniego elementu jednej z list, w zależności od tego, co nastąpi wcześniej.

Algorytm ten wymaga czasu O (h), gdzie h jest wysokością drzewa. W najgorszym przypadku O (h) jest równoważne O (n), ale jeśli drzewo jest zrównoważone, to jest tylko O ​​(log (n)). Wymaga również spacji O (h). Możliwa jest ulepszona wersja, która używa tylko stałej spacji, z kodem pokazanym w poście CEGRD

Bez względu na to, jak drzewo jest zbudowane, jeśli będzie to operacja, którą wykonasz wiele razy na drzewie bez zmiany jej w międzyczasie, istnieją inne algorytmy, których możesz użyć, które wymagają przygotowania czasu O (n) [liniowe], ale potem znalezienie para zajmuje tylko czas O (1) [stały]. Aby zapoznać się z odniesieniami do tych algorytmów, zobacz stronę z najniższym wspólnym problemem przodka w Wikipedii . (Podziękowania dla Jasona za pierwotne opublikowanie tego linku)

Zaczynając od rootwęzła i idąc w dół, jeśli znajdziesz dowolny węzeł, który ma jedno z nich plub qjako jego bezpośrednie dziecko potomne, jest to LCA. (edytuj - powinno to być, jeśli plub qjest wartością węzła, zwróć ją. W przeciwnym razie nie powiedzie się, gdy jeden z nich plub qjest bezpośrednim dzieckiem drugiego).

W przeciwnym razie, jeśli znajdziesz węzeł z pprawym (lub lewym) poddrzewem i qlewym (lub prawym) poddrzewem, to jest to LCA.

Naprawiony kod wygląda następująco:

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Poniższy kod nie działa, gdy jeden z nich jest bezpośrednim dzieckiem innego.

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is direct child of root then root is LCA.
        if(root->left==p || root->left==q || 
           root->right ==p || root->right ==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Kod w akcji

Oto działający kod w JAVA

public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }

   // If the root is one of a or b, then it is the LCA
   if (root == a || root == b) {
       return root;
   }

   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);

   // If both nodes lie in left or right then their LCA is in left or right,
   // Otherwise root is their LCA
   if (left != null && right != null) {
      return root;
   }

   return (left != null) ? left : right; 
}

Odpowiedzi udzielone do tej pory wykorzystują rekursję lub przechowują na przykład ścieżkę w pamięci.

Oba te podejścia mogą zawieść, jeśli masz bardzo głębokie drzewo.

Oto moje podejście do tego pytania. Gdy sprawdzimy głębokość (odległość od korzenia) obu węzłów, jeśli są równe, możemy bezpiecznie przejść w górę od obu węzłów w kierunku wspólnego przodka. Jeśli jedna z głębokości jest większa, powinniśmy iść w górę z głębszego węzła, pozostając w drugim.

Oto kod:

findLowestCommonAncestor(v,w):
  depth_vv = depth(v);
  depth_ww = depth(w);

  vv = v; 
  ww = w;

  while( depth_vv != depth_ww ) {
    if ( depth_vv > depth_ww ) {
      vv = parent(vv);
      depth_vv--;
    else {
      ww = parent(ww);
      depth_ww--;
    }
  }

  while( vv != ww ) {
    vv = parent(vv);
    ww = parent(ww);
  }

  return vv;    

Złożoność czasowa tego algorytmu to: O (n). Przestrzenna złożoność tego algorytmu to: O (1).

Jeśli chodzi o obliczanie głębokości, możemy najpierw zapamiętać definicję: Jeśli v jest pierwiastkiem, głębokość (v) = 0; W przeciwnym razie głębokość (v) = głębokość (rodzic (v)) + 1. Możemy obliczyć głębokość w następujący sposób:

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;

Cóż, ten rodzaj zależy od struktury Twojego drzewa binarnego. Prawdopodobnie masz jakiś sposób na znalezienie pożądanego węzła liścia, biorąc pod uwagę korzeń drzewa - po prostu zastosuj to do obu wartości, aż wybrane gałęzie się rozejdą.

Jeśli nie masz sposobu na znalezienie pożądanego liścia na podstawie korzenia, jedynym rozwiązaniem - zarówno podczas normalnej pracy, jak i znalezienia ostatniego wspólnego węzła - jest brutalne przeszukanie drzewa.

Można to znaleźć pod adresem : - http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

 tree_node_type *LowestCommonAncestor(
 tree_node_type *root , tree_node_type *p , tree_node_type *q)
 {
     tree_node_type *l , *r , *temp;
     if(root==NULL)
     {
        return NULL;
     }

    if(root->left==p || root->left==q || root->right ==p || root->right ==q)
    {
        return root;
    }
    else
    {
        l=LowestCommonAncestor(root->left , p , q);
        r=LowestCommonAncestor(root->right , p, q);

        if(l!=NULL && r!=NULL)
        {
            return root;
        }
        else
        {
        temp = (l!=NULL)?l:r;
        return temp;
        }
    }
}

Algorytm najmniej wspólnych przodków w trybie off-line Tarjana jest wystarczająco dobry (por. Także Wikipedia ). Więcej na ten temat (najniższy wspólny problem przodków) można znaleźć w Wikipedii .

Aby znaleźć wspólnego przodka dwóch węzłów: -

• Znajdź podany węzeł Node1 w drzewie za pomocą wyszukiwania binarnego i zapisz wszystkie węzły odwiedzone w tym procesie w tablicy, powiedzmy A1. Czas - O (logn), Spacja - O (logn)
• Znajdź dany węzeł 2 w drzewie za pomocą wyszukiwania binarnego i zapisz wszystkie węzły odwiedzone w tym procesie w tablicy, powiedzmy A2. Czas - O (logn), Spacja - O (logn)
• Jeśli lista A1 lub lista A2 jest pusta, to węzeł nie istnieje, więc nie ma wspólnego przodka.
• Jeśli lista A1 i lista A2 nie są puste, spójrz na listę, aż znajdziesz niepasujący węzeł. Jak tylko znajdziesz taki węzeł, to poprzedni węzeł jest wspólnym przodkiem.

To działałoby dla binarnego drzewa wyszukiwania.

Podjąłem próbę z ilustracjami i działającym kodem w Javie,

http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html

Poniższy algorytm rekurencyjny będzie działał w O (log N) dla zrównoważonego drzewa binarnego. Jeśli którykolwiek z węzłów przekazanych do funkcji getLCA () jest taki sam jak root, wówczas root będzie LCA i nie będzie potrzeby wykonywania żadnej rekusji.

Przypadki testowe. [1] Oba węzły n1 i n2 znajdują się w drzewie i znajdują się po obu stronach swojego węzła nadrzędnego. [2] Albo węzeł n1 albo n2 jest korzeniem, LCA jest korzeniem. [3] W drzewie znajduje się tylko n1 lub n2, LCA będzie albo węzłem głównym lewego poddrzewa korzenia drzewa, albo LCA będzie węzłem głównym prawego poddrzewa korzenia drzewa.

[4] Ani n1 ani n2 nie występuje w drzewie, nie ma LCA. [5] Zarówno n1, jak i n2 są w linii prostej obok siebie, LCA będzie równe n1 lub n2, które zawsze są zbliżone do korzenia drzewa.

//find the search node below root
bool findNode(node* root, node* search)
{
    //base case
    if(root == NULL)
        return false;

    if(root->val == search->val)
        return true;

    //search for the node in the left and right subtrees, if found in either return true
    return (findNode(root->left, search) || findNode(root->right, search));
}

//returns the LCA, n1 & n2 are the 2 nodes for which we are
//establishing the LCA for
node* getLCA(node* root, node* n1, node* n2)
{
    //base case
    if(root == NULL)
        return NULL;

    //If 1 of the nodes is the root then the root is the LCA
    //no need to recurse.
    if(n1 == root || n2 == root)
        return root;

    //check on which side of the root n1 and n2 reside
    bool n1OnLeft = findNode(root->left, n1);
    bool n2OnLeft = findNode(root->left, n2);

    //n1 & n2 are on different sides of the root, so root is the LCA
    if(n1OnLeft != n2OnLeft)
        return root;

    //if both n1 & n2 are on the left of the root traverse left sub tree only
    //to find the node where n1 & n2 diverge otherwise traverse right subtree
    if(n1OnLeft)
        return getLCA(root->left, n1, n2);
    else
        return getLCA(root->right, n1, n2);
}

Po prostu zejdź z całego drzewa roottak długo, jak długo oba podane węzły, powiedzmy pi q, dla którego należy znaleźć Przodka, znajdują się w tym samym poddrzewie (co oznacza, że ​​ich wartości są mniejsze lub oba są większe od korzenia).

To idzie prosto od korzenia do najmniejszego przodka, nie patrząc na resztę drzewa, więc jest prawie tak szybkie, jak to tylko możliwe. Na kilka sposobów.

Iteracyjna, przestrzeń O (1)

Pyton

def lowestCommonAncestor(self, root, p, q):
    while (root.val - p.val) * (root.val - q.val) > 0:
        root = (root.left, root.right)[p.val > root.val]
    return root

Jawa

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while ((root.val - p.val) * (root.val - q.val) > 0)
        root = p.val < root.val ? root.left : root.right;
    return root;
}

w przypadku przepełnienia zrobiłbym (root.val - (long) p.val) * (root.val - (long) q.val)

Rekursywne

Pyton

def lowestCommonAncestor(self, root, p, q):
    next = p.val < root.val > q.val and root.left or \
           p.val > root.val < q.val and root.right
    return self.lowestCommonAncestor(next, p, q) if next else root

Jawa

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    return (root.val - p.val) * (root.val - q.val) < 1 ? root :
           lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Rozważ to drzewo

Jeśli wykonamy przeglądanie w trybie postorder i preorder i znajdziemy pierwszego występującego wspólnego poprzednika i następcę, otrzymamy wspólnego przodka.

zamówienie pocztowe => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 zamówienie wstępne => 7,3,1,0,2,6,4 , 5,12,9,8,11,10,13,15,14

• np .: 1

Najmniejszy wspólny przodek 8,11

w zamówieniu pocztowym mamy => 9,14,15,13,12,7 po 8 i 11 w przedsprzedaży mamy => 7,3,1,0,2,6,4,5,12,9 przed 8 i 11

9 to pierwsza wspólna liczba występująca po 8 i 11 w zamówieniu pocztowym i przed 8 i 11 w przedsprzedaży, stąd 9 to odpowiedź

• np .: 2

Najmniejszy wspólny przodek 5,10

11,9,14,15,13,12,7 w zamówieniu pocztowym 7,3,1,0,2,6,4 w przedsprzedaży

7 to pierwsza liczba, która pojawia się po 5,10 w zamówieniu pocztowym i przed 5,10 w zamówieniu w przedsprzedaży, stąd 7 to odpowiedź

Jeśli jest to pełne drzewo binarne z dziećmi węzła x jako 2 * x i 2 * x + 1, to można to zrobić szybciej

int get_bits(unsigned int x) {
  int high = 31;
  int low = 0,mid;
  while(high>=low) {
    mid = (high+low)/2;
    if(1<<mid==x)
      return mid+1;
    if(1<<mid<x) {
      low = mid+1;
    }
    else {
      high = mid-1;
    }
  }
  if(1<<mid>x)
    return mid;
  return mid+1;
}

unsigned int Common_Ancestor(unsigned int x,unsigned int y) {

  int xbits = get_bits(x);
  int ybits = get_bits(y);
  int diff,kbits;
  unsigned int k;
  if(xbits>ybits) {
    diff = xbits-ybits;
    x = x >> diff;
  }
  else if(xbits<ybits) {
    diff = ybits-xbits;
    y = y >> diff;
  }
  k = x^y;
  kbits = get_bits(k);
  return y>>kbits;  
}

Jak to działa

1. pobierz bity potrzebne do reprezentowania x & y, które przy użyciu wyszukiwania binarnego to O (log (32))
2. wspólny przedrostek binarnej notacji x & y jest wspólnym przodkiem
3. cokolwiek jest reprezentowane przez większą liczbę bitów, jest sprowadzane do tego samego bitu przez k >> diff
4. k = x ^ y usuwa wspólny przedrostek x & y
5. znajdź bity reprezentujące pozostały przyrostek
6. przesuń x lub y o bity sufiksu, aby uzyskać wspólny przedrostek, który jest wspólnym przodkiem.

To działa, ponieważ w zasadzie należy rekurencyjnie podzielić większą liczbę przez dwa, aż obie liczby będą równe. Ta liczba jest wspólnym przodkiem. Dzielenie jest w rzeczywistości właściwą zmianą. Musimy więc znaleźć wspólny przedrostek dwóch liczb, aby znaleźć najbliższego przodka

W scali możesz:

  abstract class Tree
  case class Node(a:Int, left:Tree, right:Tree) extends Tree
  case class Leaf(a:Int) extends Tree

  def lca(tree:Tree, a:Int, b:Int):Tree = {
    tree match {
      case Node(ab,l,r) => {
        if(ab==a || ab ==b) tree else {
          val temp = lca(l,a,b);
          val temp2 = lca(r,a,b);
          if(temp!=null && temp2 !=null)
            tree
          else if (temp==null && temp2==null)
            null
          else if (temp==null) r else l
        }

      }
      case Leaf(ab) => if(ab==a || ab ==b) tree else null
    }
  }

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        return left == null ? right : right == null ? left : root;
    }

Oto sposób, w jaki można to zrobić w C ++. Starałem się, aby algorytm był jak najłatwiejszy do zrozumienia:

// Assuming that `BinaryNode_t` has `getData()`, `getLeft()` and `getRight()`
class LowestCommonAncestor
{
  typedef char type;    
  // Data members which would behave as place holders
  const BinaryNode_t* m_pLCA;
  type m_Node1, m_Node2;

  static const unsigned int TOTAL_NODES = 2;

  // The core function which actually finds the LCA; It returns the number of nodes found
  // At any point of time if the number of nodes found are 2, then it updates the `m_pLCA` and once updated, we have found it!
  unsigned int Search (const BinaryNode_t* const pNode)
  {
    if(pNode == 0)
      return 0;

    unsigned int found = 0;

    found += (pNode->getData() == m_Node1);
    found += (pNode->getData() == m_Node2);

    found += Search(pNode->getLeft()); // below condition can be after this as well
    found += Search(pNode->getRight());

    if(found == TOTAL_NODES && m_pLCA == 0)
      m_pLCA = pNode;  // found !

    return found;
  }

public:
  // Interface method which will be called externally by the client
  const BinaryNode_t* Search (const BinaryNode_t* const pHead,
                              const type node1,
                              const type node2)
  {
    // Initialize the data members of the class
    m_Node1 = node1;
    m_Node2 = node2;
    m_pLCA = 0;

    // Find the LCA, populate to `m_pLCANode` and return
    (void) Search(pHead);
    return m_pLCA;
  }
};

Jak tego użyć:

LowestCommonAncestor lca;
BinaryNode_t* pNode = lca.Search(pWhateverBinaryTreeNodeToBeginWith);
if(pNode != 0)
  ...

Najłatwiejszym sposobem znalezienia najniższego wspólnego przodka jest użycie następującego algorytmu:

Zbadaj węzeł główny

jeśli wartość1 i wartość2 są ściśle mniejsze niż wartość w węźle głównym 
    Zbadaj lewe poddrzewo
w przeciwnym razie wartość1 i wartość2 są znacznie większe niż wartość w węźle głównym 
    Zbadaj prawe poddrzewo
jeszcze
    return root

public int LCA(TreeNode root, int value 1, int value 2) {
    while (root != null) {
       if (value1 < root.data && value2 < root.data)
           return LCA(root.left, value1, value2);
       else if (value2 > root.data && value2 2 root.data)
           return LCA(root.right, value1, value2);
       else
           return root
    }

    return null;
} 

Znalazłem rozwiązanie

1. Zamów w porządku
2. Zamów w przedsprzedaży
3. Weź zamówienie pocztowe

W zależności od 3 przejść możesz zdecydować, kto jest LCA. Z LCA znajdź odległość obu węzłów. Dodaj te dwie odległości, co jest odpowiedzią.

Oto, co myślę,

1. Znajdź trasę dla pierwszego węzła i zapisz ją w arr1.
2. Zacznij znajdować trasę dla węzła 2, jednocześnie sprawdzając każdą wartość od roota do arr1.
3. czas, gdy wartość się różni, zakończ. Stara dopasowana wartość to LCA.

Złożoność: krok 1: O (n), krok 2 = ~ O (n), łącznie = ~ O (n).

Oto dwa podejścia w języku C # (.net) (oba omówione powyżej) w celach informacyjnych:

1. Rekurencyjna wersja wyszukiwania LCA w drzewie binarnym (O (N) - tak jak odwiedzany jest co najwyżej każdy węzeł) (główne punkty rozwiązania to LCA to (a) jedyny węzeł w drzewie binarnym, w którym oba elementy znajdują się po obu stronach poddrzewa (po lewej i po prawej) to LCA. (b) Nie ma też znaczenia, który węzeł jest obecny po obu stronach - początkowo starałem się zachować te informacje i oczywiście funkcja rekurencyjna stała się tak zagmatwana.

2. Przeszukiwanie obu węzłów (O (N)) i śledzenie ścieżek (zajmuje dodatkową przestrzeń - więc numer 1 jest prawdopodobnie lepszy, nawet jeśli przestrzeń jest prawdopodobnie nieistotna, jeśli drzewo binarne jest dobrze zbalansowane, ponieważ wtedy dodatkowe zużycie pamięci będzie O (log (N)).

   aby ścieżki były porównywane (zasadniczo podobne do akceptowanej odpowiedzi - ale ścieżki są obliczane przy założeniu, że węzeł wskaźnikowy nie występuje w węźle drzewa binarnego)

3. Tylko do wypełnienia ( nie dotyczy pytania ), LCA w BST (O (log (N))

4. Testy

Rekursywne:

private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode, 
            int e1, int e2)
        {
            Debug.Assert(e1 != e2);
            
            if(treeNode == null)
            {
                return null;
            }
            if((treeNode.Element == e1)
                || (treeNode.Element == e2))
            {
                //we don't care which element is present (e1 or e2), we just need to check 
                //if one of them is there
                return treeNode;
            }
            var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2);
            var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2);
            if(nLeft != null && nRight != null)
            {
                //note that this condition will be true only at least common ancestor
                return treeNode;
            }
            else if(nLeft != null)
            {
                return nLeft;
            }
            else if(nRight != null)
            {
                return nRight;
            }
            return null;
        }

gdzie powyższa prywatna wersja rekurencyjna jest wywoływana następującą metodą publiczną:

public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2)
        {
            var n = this.FindNode(this._root, e1);
            if(null == n)
            {
                throw new Exception("Element not found: " + e1);
            }
            if (e1 == e2)
            {   
                return n;
            }
            n = this.FindNode(this._root, e2);
            if (null == n)
            {
                throw new Exception("Element not found: " + e2);
            }
            var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2);
            if (null == node)
            {
                throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2));
            }
            return node;
        }

Rozwiązanie dzięki śledzeniu ścieżek obu węzłów:

public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2)
        {
            var path1 = new List<BinaryTreeNode>();
            var node1 = this.FindNodeAndPath(this._root, e1, path1);
            if(node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e1));
            }
            if(e1 == e2)
            {
                return node1;
            }
            List<BinaryTreeNode> path2 = new List<BinaryTreeNode>();
            var node2 = this.FindNodeAndPath(this._root, e2, path2);
            if (node1 == null)
            {
                throw new Exception(string.Format("Element {0} is not found", e2));
            }
            BinaryTreeNode lca = null;
            Debug.Assert(path1[0] == this._root);
            Debug.Assert(path2[0] == this._root);
            int i = 0;
            while((i < path1.Count)
                && (i < path2.Count)
                && (path2[i] == path1[i]))
            {
                lca = path1[i];
                i++;
            }
            Debug.Assert(null != lca);
            return lca;
        }

gdzie FindNodeAndPath jest zdefiniowany jako

private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List<BinaryTreeNode> path)
        {
            if(node == null)
            {
                return null;
            }
            if(node.Element == e)
            {
                path.Add(node);
                return node;
            }
            var n = this.FindNodeAndPath(node.Left, e, path);
            if(n == null)
            {
                n = this.FindNodeAndPath(node.Right, e, path);
            }
            if(n != null)
            {
                path.Insert(0, node);
                return n;
            }
            return null;
        }

BST (LCA) - niepowiązane (tylko do uzupełnienia w celach informacyjnych)

public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
        {
            //ensure both elements are there in the bst
            var n1 = this.BstFind(e1, throwIfNotFound: true);
            if(e1 == e2)
            {
                return n1;
            }
            this.BstFind(e2, throwIfNotFound: true);
            BinaryTreeNode leastCommonAcncestor = this._root;
            var iterativeNode = this._root;
            while(iterativeNode != null)
            {
                if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
                {
                    iterativeNode = iterativeNode.Left;
                }
                else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
                {
                    iterativeNode = iterativeNode.Right;
                }
                else
                {
                    //i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
                    return iterativeNode;
                }
            }
            //control will never come here
            return leastCommonAcncestor;
        }

Testy jednostkowe

[TestMethod]
        public void LeastCommonAncestorTests()
        {
            int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
            int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
            BinarySearchTree bst = new BinarySearchTree();
            foreach (int e in a)
            {
                bst.Add(e);
                bst.Delete(e);
                bst.Add(e);
            }
            for(int i = 0; i < b.Length; i++)
            {
                var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
                Assert.IsTrue(n.Element == b[i]);
                var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]);
                Assert.IsTrue(n1.Element == b[i]);
                Assert.IsTrue(n == n1);
                var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]);
                Assert.IsTrue(n2.Element == b[i]);
                Assert.IsTrue(n2 == n1);
                Assert.IsTrue(n2 == n);
            }
        }

Jeśli ktoś jest zainteresowany pseudokodem (do prac domowych na uczelni), oto jeden.

GETLCA(BINARYTREE BT, NODE A, NODE  B)
IF Root==NIL
    return NIL
ENDIF

IF Root==A OR root==B
    return Root
ENDIF

Left = GETLCA (Root.Left, A, B)
Right = GETLCA (Root.Right, A, B)

IF Left! = NIL AND Right! = NIL
    return root
ELSEIF Left! = NIL
    Return Left
ELSE
    Return Right
ENDIF

Chociaż już na to odpowiedziano, to jest moje podejście do tego problemu przy użyciu języka programowania C. Chociaż kod pokazuje binarne drzewo wyszukiwania (jeśli chodzi o insert ()), ale algorytm działa również dla drzewa binarnego. Pomysł polega na przejściu przez wszystkie węzły, które leżą od węzła A do węzła B w trakcie przechodzenia w kolejności, i wyszukanie dla nich indeksów w trakcie przechodzenia po zamówieniu. Węzeł z maksymalnym indeksem w przechodzeniu po zamówieniu jest najniższym wspólnym przodkiem.

To jest działający kod C do implementacji funkcji znajdującej najniższego wspólnego przodka w drzewie binarnym. Udostępniam również wszystkie funkcje narzędziowe itp., Ale w celu szybkiego zrozumienia przejdź do CommonAncestor ().

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>

static inline int min (int a, int b)
{
    return ((a < b) ? a : b);
}
static inline int max (int a, int b)
{
    return ((a > b) ? a : b);
}

typedef struct node_ {
    int value;
    struct node_ * left;
    struct node_ * right;
} node;

#define MAX 12

int IN_ORDER[MAX] = {0};
int POST_ORDER[MAX] = {0};

createNode(int value) 
{
    node * temp_node = (node *)malloc(sizeof(node));
    temp_node->left = temp_node->right = NULL;
    temp_node->value = value;
    return temp_node;
}

node *
insert(node * root, int value)
{
    if (!root) {
        return createNode(value);
    }

    if (root->value > value) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }

    return root;
}


/* Builds inorder traversal path in the IN array */
void
inorder(node * root, int * IN)
{
    static int i = 0;

    if (!root) return;

    inorder(root->left, IN);
    IN[i] = root->value;
    i++;
    inorder(root->right, IN);
}

/* Builds post traversal path in the POST array */

void
postorder (node * root, int * POST)
{
    static int i = 0;

    if (!root) return;

    postorder(root->left, POST);
    postorder(root->right, POST);
    POST[i] = root->value;
    i++;
}


int
findIndex(int * A, int value)
{
    int i = 0;
    for(i = 0; i< MAX; i++) {
        if(A[i] == value) return i;
    }
}
int
CommonAncestor(int val1, int val2)
{
    int in_val1, in_val2;
    int post_val1, post_val2;
    int j=0, i = 0; int max_index = -1;

    in_val1 = findIndex(IN_ORDER, val1);
    in_val2 = findIndex(IN_ORDER, val2);
    post_val1 = findIndex(POST_ORDER, val1);
    post_val2 = findIndex(POST_ORDER, val2);

    for (i = min(in_val1, in_val2); i<= max(in_val1, in_val2); i++) {
        for(j = 0; j < MAX; j++) {
            if (IN_ORDER[i] == POST_ORDER[j]) {
                if (j > max_index) {
                    max_index = j;
                }
            }
        }
    }
    printf("\ncommon ancestor of %d and %d is %d\n", val1, val2, POST_ORDER[max_index]);
    return max_index;
}
int main()
{
    node * root = NULL; 

    /* Build a tree with following values */
    //40, 20, 10, 30, 5, 15, 25, 35, 1, 80, 60, 100
    root = insert(root, 40);
    insert(root, 20);
    insert(root, 10);
    insert(root, 30);
    insert(root, 5);
    insert(root, 15);
    insert(root, 25);
    insert(root, 35);
    insert(root, 1);
    insert(root, 80);
    insert(root, 60);
    insert(root, 100);

    /* Get IN_ORDER traversal in the array */
    inorder(root, IN_ORDER);

    /* Get post order traversal in the array */
    postorder(root, POST_ORDER);

    CommonAncestor(1, 100);


}

Może być jeszcze jedno podejście. Jednak nie jest tak skuteczny, jak sugerowano już w odpowiedziach.

• Utwórz wektor ścieżki dla węzła n1.

• Utwórz drugi wektor ścieżki dla węzła n2.

• Wektor ścieżki implikujący zbiór węzłów z tego jednego przeszedłby, aby dotrzeć do danego węzła.

• Porównaj oba wektory ścieżki. Indeks, w którym się nie zgadzają, zwraca węzeł w tym indeksie - 1. To dałoby LCA.

Wady tego podejścia:

Aby obliczyć wektory ścieżki, trzeba dwukrotnie przejść przez drzewo. Potrzebujesz dodatkowej przestrzeni O (h) do przechowywania wektorów ścieżek.

Jednak jest to również łatwe do wdrożenia i zrozumienia.

Kod do obliczania wektora ścieżki:

private boolean findPathVector (TreeNode treeNode, int key, int pathVector[], int index) {

        if (treeNode == null) {
            return false;
        }

        pathVector [index++] = treeNode.getKey ();

        if (treeNode.getKey () == key) {
            return true;
        }
        if (findPathVector (treeNode.getLeftChild (), key, pathVector, index) || 
            findPathVector (treeNode.getRightChild(), key, pathVector, index)) {

            return true;        
        }

        pathVector [--index] = 0;
        return false;       
    }

Spróbuj w ten sposób

node * lca(node * root, int v1,int v2)
{

if(!root) {
            return NULL;
    }
    if(root->data == v1 || root->data == v2) {
        return root;}
    else
    {
        if((v1 > root->data && v2 < root->data) || (v1 < root->data && v2 > root->data))
        {
            return root;
        }

        if(v1 < root->data && v2 < root->data)
        {
            root = lca(root->left, v1, v2);
        }

        if(v1 > root->data && v2 > root->data)
        {
            root = lca(root->right, v1, v2);
        }
    }
return root;
}

Surowy sposób:

• W każdym węźle
  • X = znajdź, jeśli którykolwiek z n1, n2 istnieje po lewej stronie węzła
  • Y = znajdź, jeśli którykolwiek z n1, n2 istnieje po prawej stronie węzła
    • jeśli sam węzeł jest n1 || n2, dla uogólnienia możemy go nazwać albo po lewej, albo po prawej stronie.
  • Jeśli zarówno X, jak i Y są prawdziwe, to węzeł jest urzędem certyfikacji

Problem z powyższą metodą polega na tym, że "znajdź" będziemy wykonywać wiele razy, tj. Istnieje możliwość, że każdy węzeł zostanie przemierzony wiele razy. Możemy rozwiązać ten problem, jeśli uda nam się zapisać informacje, aby nie przetwarzać ich ponownie (pomyśl o programowaniu dynamicznym).

Więc zamiast znajdować każdy węzeł, prowadzimy rejestr tego, co już zostało znalezione.

Lepszy sposób:

• Sprawdzamy, czy dla danego węzła, jeśli left_set (co oznacza, że ​​n1 | n2 zostało znalezione w lewym poddrzewie) lub right_set w sposób głęboki. (UWAGA: Nadajemy samemu rootowi właściwość bycia left_set, jeśli jest to n1 | n2)
• Jeśli zarówno left_set, jak i right_set, to węzeł jest LCA.

Kod:

struct Node *
findCA(struct Node *root, struct Node *n1, struct Node *n2, int *set) {
   int left_set, right_set;
   left_set = right_set = 0;
   struct Node *leftCA, *rightCA;
   leftCA = rightCA = NULL;

   if (root == NULL) {
      return NULL;
   }
   if (root == n1 || root == n2) {
      left_set = 1;
      if (n1 == n2) {
         right_set = 1;
      }
   }

   if(!left_set) {
      leftCA = findCA(root->left, n1, n2, &left_set);
      if (leftCA) {
         return leftCA;
      }
   }
   if (!right_set) {
      rightCA= findCA(root->right, n1, n2, &right_set);
      if(rightCA) {
         return rightCA;
      }
   }

   if (left_set && right_set) {
      return root;
   } else {
      *set = (left_set || right_set);
      return NULL;
   }
}

Kod wyszukiwania szerokości, aby upewnić się, że oba węzły znajdują się w drzewie. Dopiero wtedy przejdź do wyszukiwania LCA. Prosimy o komentarz, jeśli masz jakieś sugestie dotyczące ulepszeń. Myślę, że prawdopodobnie możemy oznaczyć je jako odwiedzone i ponownie rozpocząć wyszukiwanie w pewnym momencie, w którym przerwaliśmy, aby poprawić drugi węzeł (jeśli nie zostanie znaleziony ODWIEDZONY)

public class searchTree {
    static boolean v1=false,v2=false;
    public static boolean bfs(Treenode root, int value){
         if(root==null){
           return false;
     }
    Queue<Treenode> q1 = new LinkedList<Treenode>();

    q1.add(root);
    while(!q1.isEmpty())
    {
        Treenode temp = q1.peek();

        if(temp!=null) {
            q1.remove();
            if (temp.value == value) return true;
            if (temp.left != null) q1.add(temp.left);
            if (temp.right != null) q1.add(temp.right);
        }
    }
    return false;

}
public static Treenode lcaHelper(Treenode head, int x,int y){

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

    if(head.value == x || head.value ==y){
        if (head.value == y){
            v2 = true;
            return head;
        }
        else {
            v1 = true;
            return head;
        }
    }

    Treenode left = lcaHelper(head.left, x, y);
    Treenode right = lcaHelper(head.right,x,y);

    if(left!=null && right!=null){
        return head;
    }
    return (left!=null) ? left:right;
}

public static int lca(Treenode head, int h1, int h2) {
    v1 = bfs(head,h1);
    v2 = bfs(head,h2);
    if(v1 && v2){
        Treenode lca = lcaHelper(head,h1,h2);
        return lca.value;
    }
    return -1;
}
}

Masz rację, że bez węzła nadrzędnego rozwiązanie z przechodzeniem da ci złożoność czasową O (n).

Podejście przemierzające Załóżmy, że znajdujesz LCA dla węzłów A i B, najprostszym podejściem jest najpierw pobranie ścieżki od katalogu głównego do A, a następnie ścieżki od katalogu głównego do B. Gdy masz już te dwie ścieżki, możesz je łatwo iterować i znajdź ostatni wspólny węzeł, który jest najniższym wspólnym przodkiem A i B.

Rozwiązanie rekurencyjne Innym podejściem jest użycie rekurencji. Po pierwsze, możemy pobrać LCA z lewego i prawego drzewa (jeśli istnieje). Jeśli jeden z A lub B jest węzłem głównym, to korzeń jest LCA i po prostu zwracamy pierwiastek, który jest punktem końcowym rekurencji. Kiedy będziemy dalej dzielić drzewo na podgrupy, w końcu trafimy na A i B.

Aby połączyć rozwiązania podproblemów, jeśli LCA (lewe drzewo) zwraca węzeł, wiemy, że zarówno A, jak i B znajdują się w lewym drzewie, a zwrócony węzeł jest wynikiem końcowym. Jeśli zarówno LCA (lewy), jak i LCA (prawy) zwracają niepuste węzły, oznacza to, że A i B znajdują się odpowiednio w lewym i prawym drzewie. W tym przypadku węzeł główny jest najniższym wspólnym węzłem.

Sprawdź Najniższy wspólny przodek, aby uzyskać szczegółową analizę i rozwiązanie.

Niektóre rozwiązania zakładają, że istnieje odniesienie do węzła głównego, inne zakładają, że drzewo jest BST. Udostępnianie mojego rozwiązania za pomocą hashmap, bez odniesienia do rootwęzła i drzewa, może być BST lub inne niż BST:

    var leftParent : Node? = left
    var rightParent : Node? = right
    var map = [data : Node?]()

    while leftParent != nil {
        map[(leftParent?.data)!] = leftParent
        leftParent = leftParent?.parent
    }

    while rightParent != nil {
        if let common = map[(rightParent?.data)!] {
            return common
        }
        rightParent = rightParent?.parent
    }

Rozwiązanie 1: rekurencyjne - szybciej

• Chodzi o to, aby przejść przez drzewo, zaczynając od korzenia. Jeśli którykolwiek z podanych kluczy p i q jest zgodny z rootem, to root jest LCA, zakładając, że oba klucze są obecne. Jeśli root nie pasuje do żadnego z kluczy, powtarzamy dla lewego i prawego poddrzewa.
• Węzeł, który ma jeden klucz obecny w lewym poddrzewie, a drugi klucz w prawym poddrzewie, to LCA. Jeśli oba klucze znajdują się w lewym poddrzewie, to lewe poddrzewo również ma LCA, w przeciwnym razie LCA leży w prawym poddrzewie.

• Złożoność czasowa: O (n)
• Złożoność przestrzeni: O (h) - dla rekurencyjnego stosu wywołań

class Solution 
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        if(root == null || root == p  || root == q)
            return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null)
            return right;
        else if(right == null)
            return left;
        else
            return root;    // If(left != null && right != null)
    }
}

Rozwiązanie 2: Iteracyjne - Korzystanie ze wskaźników nadrzędnych - Wolniej

• Utwórz pustą tabelę skrótów.
• Wstaw p i wszystkich jego przodków do tablicy skrótów.
• Sprawdź, czy q lub którykolwiek z jego przodków istnieje w tablicy mieszania, jeśli tak, zwróć pierwszego istniejącego przodka.

• Złożoność czasowa: O (n) - W najgorszym przypadku możemy odwiedzać wszystkie węzły drzewa binarnego.
• Złożoność przestrzeni: O (n) - Przestrzeń użyta we wskaźniku nadrzędnym Hash-table, ancestor_set i queue, będzie wynosić O (n) każdy.

class Solution
{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        HashMap<TreeNode, TreeNode> parent_map = new HashMap<>();
        HashSet<TreeNode> ancestors_set = new HashSet<>();
        Queue<TreeNode> queue = new LinkedList<>();

        parent_map.put(root, null);
        queue.add(root);

        while(!parent_map.containsKey(p) || !parent_map.containsKey(q))
        {
            TreeNode node = queue.poll();

            if(node.left != null)
            {
                parent_map.put(node.left, node);
                queue.add(node.left);
            }
            if(node.right != null)
            {
                parent_map.put(node.right, node);
                queue.add(node.right);
            }
        }

        while(p != null)
        {
            ancestors_set.add(p);
            p = parent_map.get(p);
        }

        while(!ancestors_set.contains(q))
            q = parent_map.get(q);

        return q;
    }
}