Wie finde ich den niedrigsten gemeinsamen Vorfahren von zwei Knoten in einem Binärbaum?

Der Binärbaum hier muss nicht unbedingt ein Binärsuchbaum sein.
Die Struktur könnte angenommen werden als -

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

Die maximale Lösung, die ich mit einem Freund finden konnte, war etwas in dieser Art -
Betrachten Sie diesen Binärbaum :

Die Inorder Traversal ergibt - 8, 4, 9, 2, 5, 1, 6, 3, 7

Und die Nachbestellungsdurchquerung ergibt - 8, 9, 4, 5, 2, 6, 7, 3, 1

Wenn wir zum Beispiel den gemeinsamen Vorfahren der Knoten 8 und 5 finden wollen, erstellen wir eine Liste aller Knoten, die zwischen 8 und 5 in der Inorder-Tree-Traversal liegen, in diesem Fall [4, 9 , 2]. Dann prüfen wir, welcher Knoten in dieser Liste zuletzt in der Nachbestellungsdurchquerung erscheint, nämlich 2. Daher ist der gemeinsame Vorfahr für 8 und 5 2.

Die Komplexität für diesen Algorithmus ist meines Erachtens O (n) (O (n) für Inorder / Postorder-Traversale, der Rest der Schritte ist wiederum O (n), da es sich nur um einfache Iterationen in Arrays handelt. Es besteht jedoch eine große Wahrscheinlichkeit, dass dies falsch ist. :-)

Aber dies ist ein sehr grober Ansatz, und ich bin mir nicht sicher, ob er in einigen Fällen zusammenbricht. Gibt es eine andere (möglicherweise optimalere) Lösung für dieses Problem?

Nick Johnson hat Recht, dass ein O (n) -Zeitkomplexitätsalgorithmus das Beste ist, was Sie tun können, wenn Sie keine übergeordneten Zeiger haben.) Eine einfache rekursive Version dieses Algorithmus finden Sie im Code in Kindings Beitrag , der in O (n) -Zeit ausgeführt wird .

Beachten Sie jedoch, dass ein verbesserter Algorithmus möglich ist, wenn Ihre Knoten übergeordnete Zeiger haben. Erstellen Sie für beide fraglichen Knoten eine Liste mit dem Pfad von der Wurzel zum Knoten, indem Sie am Knoten beginnen und das übergeordnete Element von vorne einfügen.

Für 8 in Ihrem Beispiel erhalten Sie (zeigt Schritte): {4}, {2, 4}, {1, 2, 4}

Machen Sie dasselbe für Ihren anderen fraglichen Knoten, was zu (nicht gezeigten Schritten) führt: {1, 2}

Vergleichen Sie nun die beiden Listen, die Sie erstellt haben, und suchen Sie nach dem ersten Element, bei dem sich die Liste unterscheidet, oder nach dem letzten Element einer der Listen, je nachdem, was zuerst eintritt.

Dieser Algorithmus benötigt O (h) Zeit, wobei h die Höhe des Baums ist. Im schlimmsten Fall entspricht O (h) O (n), aber wenn der Baum ausgeglichen ist, ist dies nur O (log (n)). Es benötigt auch O (h) Platz. Es ist eine verbesserte Version möglich, die nur konstanten Speicherplatz verwendet, wobei der Code im Beitrag von CEGRD angezeigt wird

Unabhängig davon, wie der Baum aufgebaut ist, können Sie andere Algorithmen verwenden, die eine O (n) [lineare] Zeitvorbereitung erfordern, aber dann eine finden, wenn dies eine Operation ist, die Sie mehrmals am Baum ausführen, ohne sie dazwischen zu ändern Paar benötigt nur O (1) [konstant] Zeit. Verweise auf diese Algorithmen finden Sie auf der Seite mit dem niedrigsten Problem mit gemeinsamen Vorfahren auf Wikipedia . (Dank an Jason für die ursprüngliche Veröffentlichung dieses Links)

Ausgehend vom rootKnoten und nach unten bewegend, wenn Sie einen Knoten finden, der entweder poder qals direktes untergeordnetes Element hat, dann ist es die Ökobilanz. (edit - dies sollte , wenn sein poder qist der Wert des Knotens, es zurückgeben Sonst wird es fehlschlagen , wenn man von. poder qein direktes Kind des anderen ist.)

Andernfalls ist es die Ökobilanz, wenn Sie einen Knoten mit pseinem rechten (oder linken) Teilbaum und qseinem linken (oder rechten) Teilbaum finden.

Der feste Code sieht folgendermaßen aus:

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

Der folgende Code schlägt fehl, wenn einer der beiden das direkte Kind eines anderen ist.

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

Code in Aktion

Hier ist der Arbeitscode in 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; 
}

Die bisher gegebenen Antworten verwenden eine Rekursion oder speichern beispielsweise einen Pfad im Speicher.

Beide Ansätze können fehlschlagen, wenn Sie einen sehr tiefen Baum haben.

Hier ist meine Meinung zu dieser Frage. Wenn wir die Tiefe (Abstand von der Wurzel) beider Knoten überprüfen und diese gleich sind, können wir uns sicher von beiden Knoten nach oben zum gemeinsamen Vorfahren bewegen. Wenn eine der Tiefen größer ist, sollten wir uns vom tieferen Knoten nach oben bewegen, während wir im anderen bleiben.

Hier ist der Code:

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;    

Die zeitliche Komplexität dieses Algorithmus ist: O (n). Die räumliche Komplexität dieses Algorithmus ist: O (1).

In Bezug auf die Berechnung der Tiefe können wir uns zunächst an die Definition erinnern: Wenn v Wurzel ist, ist Tiefe (v) = 0; Andernfalls ist Tiefe (v) = Tiefe (Eltern (v)) + 1. Wir können die Tiefe wie folgt berechnen:

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

Nun, diese Art hängt davon ab, wie Ihr Binärbaum strukturiert ist. Vermutlich haben Sie eine Möglichkeit, den gewünschten Blattknoten anhand der Wurzel des Baums zu finden. Wenden Sie diesen einfach auf beide Werte an, bis die von Ihnen ausgewählten Zweige voneinander abweichen.

Wenn Sie angesichts der Wurzel keine Möglichkeit haben, das gewünschte Blatt zu finden, ist Ihre einzige Lösung - sowohl im normalen Betrieb als auch zum Auffinden des letzten gemeinsamen Knotens - eine Brute-Force-Suche des Baums.

Dies finden Sie unter: - 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;
        }
    }
}

Tarjans Offline-Algorithmus für die am wenigsten verbreiteten Vorfahren ist gut genug (vgl. Auch Wikipedia ). Es gibt mehr über das Problem (das niedrigste gemeinsame Vorfahrenproblem) auf Wikipedia .

So ermitteln Sie den gemeinsamen Vorfahren zweier Knoten: -

• Suchen Sie den angegebenen Knoten Node1 im Baum mithilfe der binären Suche und speichern Sie alle in diesem Prozess besuchten Knoten in einem Array, z. B. A1. Zeit - O (logn), Raum - O (logn)
• Suchen Sie den angegebenen Knoten2 im Baum mithilfe der binären Suche und speichern Sie alle in diesem Prozess besuchten Knoten in einem Array, z. B. A2. Zeit - O (logn), Raum - O (logn)
• Wenn die A1-Liste oder die A2-Liste leer ist, existiert der Knoten nicht, sodass es keinen gemeinsamen Vorfahren gibt.
• Wenn die A1-Liste und die A2-Liste nicht leer sind, überprüfen Sie die Liste, bis Sie einen nicht übereinstimmenden Knoten finden. Sobald Sie einen solchen Knoten finden, ist der vorhergehende Knoten ein gemeinsamer Vorfahr.

Dies würde für den binären Suchbaum funktionieren.

Ich habe einen Versuch mit illustrativen Bildern und Arbeitscode in Java gemacht,

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

Der folgende rekursive Algorithmus wird in O (log N) für einen ausgeglichenen Binärbaum ausgeführt. Wenn einer der an die Funktion getLCA () übergebenen Knoten mit dem Stamm identisch ist, ist der Stamm die Ökobilanz, und es ist keine erneute Diskussion erforderlich.

Testfälle. [1] Beide Knoten n1 und n2 befinden sich im Baum und befinden sich auf beiden Seiten ihres übergeordneten Knotens. [2] Entweder ist der Knoten n1 oder n2 die Wurzel, die Ökobilanz ist die Wurzel. [3] Nur n1 oder n2 befindet sich im Baum. Die Ökobilanz ist entweder der Wurzelknoten des linken Teilbaums der Baumwurzel oder die Ökobilanz ist der Wurzelknoten des rechten Teilbaums der Baumwurzel.

[4] Weder n1 noch n2 befinden sich im Baum, es gibt keine Ökobilanz. [5] Sowohl n1 als auch n2 liegen in einer geraden Linie nebeneinander. Die Ökobilanz besteht entweder aus n1 oder n2, je nachdem, welcher Wert nahe an der Wurzel des Baums liegt.

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

Gehen Sie einfach vom ganzen Baum herunter, rootsolange beide Knoten vorhanden sind, sagen wir pundq , für die Ancestor gefunden werden muss, im selben Unterbaum befinden (was bedeutet, dass ihre Werte beide kleiner oder beide größer als die Wurzeln sind).

Dies geht direkt von der Wurzel zum kleinsten gemeinsamen Vorfahren, ohne auf den Rest des Baumes zu schauen, also ist es so schnell wie es nur geht. Ein paar Möglichkeiten, es zu tun.

Iterativer O (1) -Raum

Python

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

Java

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

im Falle eines Überlaufs würde ich tun (root.val - (long) p.val) * (root.val - (long) q.val)

Rekursiv

Python

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

Java

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
}

Betrachten Sie diesen Baum

Wenn wir Nachbestellungen und Vorbestellungen durchführen und den ersten gemeinsamen Vorgänger und Nachfolger finden, erhalten wir den gemeinsamen Vorfahren.

Nachbestellung => 0,2,1,5,4,6,3,8,10,11,9,14,15,13,12,7 Vorbestellung => 7,3,1,0,2,6,4 5,12,9,8,11,10,13,15,14

• zB: 1

Am wenigsten gemeinsamer Vorfahr von 8,11

in der Nachbestellung haben wir => 9,14,15,13,12,7 nach 8 & 11 in der Vorbestellung haben wir => 7,3,1,0,2,6,4,5,12,9 vor 8 & 11

9 ist die erste gebräuchliche Zahl, die nach 8 und 11 in der Nachbestellung und vor 8 und 11 in der Vorbestellung auftritt, daher ist 9 die Antwort

• zB: 2

Am wenigsten gemeinsamer Vorfahr von 5,10

11,9,14,15,13,12,7 in Nachbestellung 7,3,1,0,2,6,4 in Vorbestellung

7 ist die erste Zahl, die nach 5,10 in der Nachbestellung und vor 5,10 in der Vorbestellung auftritt, daher ist 7 die Antwort

Wenn es sich um einen vollständigen Binärbaum mit untergeordneten Knoten des Knotens x als 2 * x und 2 * x + 1 handelt, gibt es einen schnelleren Weg, dies zu tun

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

Wie funktioniert es

1. Holen Sie sich die zur Darstellung von x & y benötigten Bits, die bei Verwendung der binären Suche O sind (log (32)).
2. Das gemeinsame Präfix der binären Notation von x & y ist der gemeinsame Vorfahr
3. was auch immer durch eine größere Anzahl von Bits dargestellt wird, wird durch k >> diff auf dasselbe Bit gebracht
4. k = x ^ y löscht das gemeinsame Präfix von x & y
5. Finden Sie Bits, die das verbleibende Suffix darstellen
6. Verschieben Sie x oder y um Suffixbits, um das gemeinsame Präfix zu erhalten, das der gemeinsame Vorfahr ist.

Dies funktioniert, weil die größere Zahl im Grunde rekursiv durch zwei geteilt wird, bis beide Zahlen gleich sind. Diese Zahl ist der gemeinsame Vorfahr. Teilen ist effektiv die richtige Verschiebung. Wir müssen also ein gemeinsames Präfix von zwei Zahlen finden, um den nächsten Vorfahren zu finden

In Scala können Sie:

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

Hier ist die C ++ - Methode. Habe versucht, den Algorithmus so einfach wie möglich zu halten:

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

Wie man es benutzt:

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

Der einfachste Weg, den niedrigsten gemeinsamen Vorfahren zu finden, ist der folgende Algorithmus:

Untersuchen Sie den Wurzelknoten

wenn value1 und value2 streng kleiner sind als der Wert am Wurzelknoten 
    Untersuche den linken Teilbaum
Andernfalls, wenn Wert1 und Wert2 streng größer sind als der Wert am Wurzelknoten 
    Untersuche den rechten Teilbaum
sonst
    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;
} 

Ich habe eine Lösung gefunden

1. Inorder nehmen
2. Vorbestellung nehmen
3. Nachbestellung annehmen

Abhängig von 3 Durchquerungen können Sie entscheiden, wer die Ökobilanz ist. Von der Ökobilanz finden Sie die Entfernung beider Knoten. Addiere diese beiden Abstände, das ist die Antwort.

Hier ist was ich denke,

1. Suchen Sie die Route für den ersten Knoten und speichern Sie sie in arr1.
2. Suchen Sie die Route für den Knoten 2, und überprüfen Sie dabei jeden Wert von root bis arr1.
3. Wenn sich der Wert unterscheidet, beenden Sie den Vorgang. Der alte übereinstimmende Wert ist die Ökobilanz.

Komplexität: Schritt 1: O (n), Schritt 2 = ~ O (n), gesamt = ~ O (n).

Hier sind zwei Ansätze in c # (.net) (beide oben diskutiert) als Referenz:

1. Rekursive Version des Findens der Ökobilanz im Binärbaum (O (N) - da höchstens jeder Knoten besucht wird) (Hauptpunkte der Lösung ist die Ökobilanz ist (a) der einzige Knoten im Binärbaum, bei dem sich beide Elemente auf beiden Seiten der Teilbäume befinden (links) und richtig) ist LCA. (b) Und es spielt auch keine Rolle, welcher Knoten auf beiden Seiten vorhanden ist - anfangs habe ich versucht, diese Informationen beizubehalten, und offensichtlich wurde die rekursive Funktion so verwirrend. Als ich sie erkannte, wurde sie sehr elegant.

2. Das Durchsuchen beider Knoten (O (N)) und das Verfolgen von Pfaden (verwendet zusätzlichen Speicherplatz - daher ist # 1 wahrscheinlich überlegen, auch wenn der Speicherplatz wahrscheinlich vernachlässigbar ist, wenn der Binärbaum gut ausbalanciert ist, da dann nur zusätzlicher Speicherverbrauch erforderlich ist O (log (N)).

   so dass die Pfade verglichen werden (im Wesentlichen ähnlich der akzeptierten Antwort - aber die Pfade werden berechnet, indem angenommen wird, dass der Zeigerknoten nicht im binären Baumknoten vorhanden ist)

3. Nur für den Abschluss ( nicht im Zusammenhang mit Frage ), Ökobilanz in BST (O (log (N))

4. Tests

Rekursiv:

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

Dabei wird die oben genannte private rekursive Version mit der folgenden öffentlichen Methode aufgerufen:

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

Lösung durch Verfolgen der Pfade beider Knoten:

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

Dabei ist FindNodeAndPath definiert als

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) - nicht verwandt (nur zur Vervollständigung als Referenz)

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

Unit Tests

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

Wenn jemand an Pseudocode interessiert ist (für Hausarbeiten an der Universität), ist hier einer.

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

Obwohl dies bereits beantwortet wurde, ist dies mein Ansatz für dieses Problem mit der Programmiersprache C. Der Code zeigt zwar einen binären Suchbaum (soweit insert () betroffen ist), aber der Algorithmus funktioniert auch für einen binären Baum. Die Idee ist, alle Knoten, die von Knoten A zu Knoten B liegen, bei der Inorder Traversal zu durchlaufen und die Indizes für diese in der Post Order Traversal nachzuschlagen. Der Knoten mit dem maximalen Index beim Durchlaufen der Nachbestellung ist der niedrigste gemeinsame Vorfahr.

Dies ist ein funktionierender C-Code zum Implementieren einer Funktion zum Finden des niedrigsten gemeinsamen Vorfahren in einem Binärbaum. Ich biete auch alle Dienstprogrammfunktionen usw. an, springe aber zum schnellen Verständnis zu 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);


}

Es kann noch einen Ansatz geben. Es ist jedoch nicht so effizient wie das, was bereits in den Antworten vorgeschlagen wurde.

• Erstellen Sie einen Pfadvektor für den Knoten n1.

• Erstellen Sie einen zweiten Pfadvektor für den Knoten n2.

• Ein Pfadvektor, der impliziert, dass die gesetzten Knoten von diesem durchlaufen werden, um den fraglichen Knoten zu erreichen.

• Vergleichen Sie beide Pfadvektoren. Der Index, bei dem sie nicht übereinstimmen, gibt den Knoten an diesem Index zurück - 1. Dies würde die Ökobilanz ergeben.

Nachteile für diesen Ansatz:

Sie müssen den Baum zweimal durchlaufen, um die Pfadvektoren zu berechnen. Benötigen Sie zusätzlichen O (h) Speicherplatz, um Pfadvektoren zu speichern.

Dies ist jedoch auch leicht zu implementieren und zu verstehen.

Code zur Berechnung des Pfadvektors:

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

Versuchen Sie es so

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

Grober Weg:

• An jedem Knoten
  • X = finde heraus, ob eines der n1, n2 auf der linken Seite des Knotens existiert
  • Y = finde, ob eines der n1, n2 auf der rechten Seite des Knotens existiert
    • wenn der Knoten selbst n1 || ist n2 können wir es zum Zwecke der Verallgemeinerung entweder links oder rechts nennen.
  • Wenn sowohl X als auch Y wahr sind, ist der Knoten die Zertifizierungsstelle

Das Problem mit der obigen Methode ist, dass wir das "Finden" mehrmals durchführen, dh es besteht die Möglichkeit, dass jeder Knoten mehrmals durchlaufen wird. Wir können dieses Problem lösen, wenn wir die Informationen aufzeichnen können, um sie nicht erneut zu verarbeiten (denken Sie an dynamische Programmierung).

Anstatt jeden Knoten zu finden, führen wir Aufzeichnungen darüber, was bereits gefunden wurde.

Besserer Weg:

• Wir prüfen, ob für einen bestimmten Knoten left_set (dh entweder n1 | n2 wurde im linken Teilbaum gefunden) oder right_set in einer ersten Tiefe. (HINWEIS: Wir geben der Wurzel selbst die Eigenschaft, left_set zu sein, wenn sie entweder n1 | n2 ist.)
• Wenn sowohl left_set als auch right_set, ist der Knoten eine Ökobilanz.

Code:

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

Code für eine Breite Erste Suche, um sicherzustellen, dass sich beide Knoten im Baum befinden. Erst dann fahren Sie mit der LCA-Suche fort. Bitte kommentieren Sie, wenn Sie Verbesserungsvorschläge haben. Ich denke, wir können sie wahrscheinlich als besucht markieren und die Suche an einem bestimmten Punkt neu starten, an dem wir aufgehört haben, um den zweiten Knoten zu verbessern (falls er nicht BESUCHT gefunden wird).

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

Sie haben Recht, dass eine Lösung mit Durchquerung ohne einen übergeordneten Knoten eine Komplexität von O (n) Zeit ergibt.

Traversal-Ansatz Angenommen, Sie finden eine Ökobilanz für Knoten A und B. Der einfachste Ansatz besteht darin, zuerst den Pfad von Root zu A und dann den Pfad von Root zu B abzurufen. Sobald Sie diese beiden Pfade haben, können Sie sie problemlos durchlaufen und finde den letzten gemeinsamen Knoten, der der niedrigste gemeinsame Vorfahr von A und B ist.

Rekursive Lösung Ein anderer Ansatz ist die Verwendung der Rekursion. Erstens können wir die Ökobilanz sowohl vom linken als auch vom rechten Baum abrufen (falls vorhanden). Wenn entweder A oder B der Wurzelknoten ist, dann ist die Wurzel die Ökobilanz und wir geben nur die Wurzel zurück, die der Endpunkt der Rekursion ist. Wenn wir den Baum weiter in Unterbäume unterteilen, treffen wir schließlich entweder A oder B.

Um Teilproblemlösungen zu kombinieren, wissen wir, dass sowohl A als auch B im linken Baum lokalisiert sind und der zurückgegebene Knoten das Endergebnis ist, wenn LCA (linker Baum) einen Knoten zurückgibt. Wenn sowohl LCA (links) als auch LCA (rechts) nicht leere Knoten zurückgeben, bedeutet dies, dass sich A und B im linken bzw. rechten Baum befinden. In diesem Fall ist der Wurzelknoten der niedrigste gemeinsame Knoten.

Überprüfen Sie den niedrigsten gemeinsamen Vorfahren auf detaillierte Analyse und Lösung.

Bei einigen Lösungen wird davon ausgegangen, dass auf den Stammknoten verwiesen wird, bei anderen wird davon ausgegangen, dass der Baum eine BST ist. Das Teilen meiner Lösung mithilfe von Hashmap ohne Bezug auf rootKnoten und Baum kann BST oder Nicht-BST sein:

    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
    }

Lösung 1: Rekursiv - Schneller

• Die Idee ist, den Baum ausgehend von der Wurzel zu durchqueren. Wenn einer der angegebenen Schlüssel p und q mit root übereinstimmt, ist root LCA, vorausgesetzt, beide Schlüssel sind vorhanden. Wenn root nicht mit einem der Schlüssel übereinstimmt, greifen wir auf den linken und rechten Teilbaum zurück.
• Der Knoten, bei dem ein Schlüssel im linken Teilbaum und der andere Schlüssel im rechten Teilbaum vorhanden ist, ist die Ökobilanz. Wenn beide Schlüssel im linken Teilbaum liegen, hat der linke Teilbaum auch die Ökobilanz, andernfalls liegt die Ökobilanz im rechten Teilbaum.

• Zeitkomplexität: O (n)
• Raumkomplexität: O (h) - für rekursiven Aufrufstapel

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

Lösung 2: Iterativ - Verwenden von übergeordneten Zeigern - Langsamer

• Erstellen Sie eine leere Hash-Tabelle.
• Fügen Sie p und alle seine Vorfahren in die Hash-Tabelle ein.
• Überprüfen Sie, ob q oder einer seiner Vorfahren in der Hash-Tabelle vorhanden ist. Wenn ja, geben Sie den ersten vorhandenen Vorfahren zurück.

• Zeitkomplexität: O (n) - Im schlimmsten Fall besuchen wir möglicherweise alle Knoten des Binärbaums.
• Raumkomplexität: O (n) - Der Raum, in dem die übergeordnete Zeiger-Hash-Tabelle ancestor_set und die Warteschlange verwendet werden, ist jeweils O (n).

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