wake-up-neo.com

Wie finde ich den niedrigsten gemeinsamen Vorfahren zweier Knoten in einem binären Baum?

Der binäre Baum ist hier nicht notwendigerweise ein binärer Suchbaum.
.__ Die Struktur könnte als

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

Die maximale Lösung, die ich mit einem Freund ausarbeiten konnte, war so etwas -
Betrachten Sie diesen binären Baum :

Binärer Baum http://lcm.csa.iisc.ernet.in/dsa/img151.gif

Die Ordnung der Ordnung ergibt - 8, 4, 9, 2, 5, 1, 6, 3, 7

Und die Nachbestellungen ergeben - 8, 9, 4, 5, 2, 6, 7, 3, 1

Wenn wir zum Beispiel den gemeinsamen Vorfahren der Knoten 8 und 5 finden möchten, erstellen wir eine Liste aller Knoten, die zwischen 8 und 5 im Inorder-Tree-Durchlauf liegen, was in diesem Fall zufällig [4, 9 ist , 2]. Dann prüfen wir, welcher Knoten in dieser Liste als letztes im Postorder-Durchlauf erscheint. Dies ist 2. Daher ist der gemeinsame Vorgänger für 8 und 5 2.

Ich glaube, die Komplexität für diesen Algorithmus ist O(n) (O (n)) für Inorder/Postorder-Traversierungen, der Rest der Schritte ist wieder O(n), da sie nicht mehr als einfach sind Iterationen in Arrays). Es besteht jedoch eine große Chance, dass dies falsch ist. :-)

Dies ist jedoch eine sehr grobe Herangehensweise, und ich bin mir nicht sicher, ob es aus irgendeinem Grund zusammenbricht. Gibt es eine andere (möglicherweise optimalere) Lösung für dieses Problem?

177
Siddhant

Nick Johnson ist richtig, dass ein an O(n) Zeitkomplexitätsalgorithmus der beste ist, den Sie tun können, wenn Sie keine übergeordneten Zeiger haben.) Eine einfache rekursive Version dieses Algorithmus finden Sie in dem Code in Kindings Beitrag die in O(n) Zeit läuft.

Denken Sie jedoch daran, dass ein verbesserter Algorithmus möglich ist, wenn Ihre Knoten über übergeordnete Zeiger verfügen. Erstellen Sie für beide fraglichen Knoten eine Liste mit dem Pfad vom Stamm zum Knoten, indem Sie am Knoten beginnen und das übergeordnete Element von vorne einfügen.

Für 8 in Ihrem Beispiel erhalten Sie also folgende Schritte: {4}, {2, 4}, {1, 2, 4}

Machen Sie dasselbe für Ihren anderen betroffenen Knoten, und führen Sie dazu die folgenden Schritte: {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 dem letzten Element einer der Listen, je nachdem, was zuerst eintritt.

Dieser Algorithmus erfordert O(h) Zeit, wobei h die Höhe des Baums ist. Im schlimmsten Fall O(h) ist Äquivalent zu O (n), aber wenn der Baum ausgeglichen ist, ist dies nur O (log (n)). Es erfordert auch O(h) Platz. Eine verbesserte Version ist möglich, die nur konstanten Speicherplatz verwendet. Der Code wird in CEGRDs Beitrag angezeigt.


Unabhängig davon, wie die Baumstruktur aufgebaut ist: Wenn dies eine Operation ist, die Sie in der Baumstruktur viele Male ausführen, ohne sie dazwischen zu ändern, gibt es andere Algorithmen, die Sie verwenden können O(n) [linear] Zeit Vorbereitung, aber dann ein Paar zu finden, dauert nur O(1) [Konstante] Zeit. Verweise auf diese Algorithmen finden Sie auf der Seite mit dem niedrigsten gemeinsamen Vorfahren in Wikipedia . (Kredit an Jason für das ursprüngliche Posten dieses Links)

69
Kevin Cathcart

Wenn Sie einen Knoten mit root oder p als direktem untergeordneten Knoten suchen, gehen Sie vom q-Knoten aus und bewegen sich nach unten. Wenn Sie einen Knoten finden, der dessen direktes untergeordnetes Element ist, handelt es sich dabei um die LCA. (edit - Dies sollte sein, wenn p oder q der Wert des Knotens ist, geben Sie ihn zurück. Andernfalls schlägt der Vorgang fehl, wenn p oder q ein direktes untergeordnetes Element des anderen sind.)

Andernfalls, wenn Sie einen Knoten mit p im rechten (oder linken) Teilbaum und q im linken (oder rechten) Teilbaum finden, ist dies die LCA.

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 direkten untergeordneten Elemente von 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

105
codaddict

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; 
}
48
Akash Verma

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

Beide Ansätze schlagen möglicherweise fehl, 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, wenn sie gleich sind, können wir sicher von beiden Knoten auf den gemeinsamen Vorfahren aufsteigen. 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).

Bezüglich der 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 (übergeordnetes (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;
26
CEGRD

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 ihn einfach auf beide Werte an, bis die von Ihnen ausgewählten Zweige abweichen.

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

7
Nick Johnson

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

Um den gemeinsamen Vorfahren zweier Knoten herauszufinden: - 

  • Suchen Sie den angegebenen Knoten Node1 in der Baumstruktur mithilfe der binären Suche, und speichern Sie alle in diesem Prozess besuchten Knoten in einem Array, z. B. A1. Zeit - O (logn), Leerzeichen - O (logn)
  • Suchen Sie den angegebenen Knoten mit Hilfe der binären Suche in der Baumstruktur und speichern Sie alle in diesem Prozess besuchten Knoten in einem Array, z. B. A2. Zeit - O (logn), Leerzeichen - O (logn)
  • Wenn die A1-Liste oder A2-Liste leer ist, existiert der Knoten nicht, so dass es keinen gemeinsamen Vorfahren gibt.
  • Wenn A1-Liste und A2-Liste nicht leer sind, schauen Sie in die Liste, bis Sie einen nicht übereinstimmenden Knoten finden. Sobald Sie einen solchen Knoten finden, ist der Knoten davor ein gemeinsamer Vorfahr.

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

5
Vipin

Tarjans Offline-Algorithmus der am wenigsten verbreiteten Vorfahren ist gut genug (vgl. Auch Wikipedia ). Auf Wikipedia gibt es mehr über das Problem (das niedrigste gemeinsame Vorfahrenproblem).

5
jason

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

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

3
bragboy

Der folgende rekursive Algorithmus wird in O (log N) für einen ausgeglichenen Binärbaum ausgeführt. Wenn einer der an die getLCA () - Funktion übergebenen Knoten mit dem Stamm identisch ist, ist der Stamm der LCA, und es ist nicht erforderlich, eine erneute Untersuchung durchzuführen.

Testfälle. [1] Beide Knoten n1 und n2 befinden sich in der Baumstruktur und befinden sich auf beiden Seiten ihres übergeordneten Knotens . [2] Jeder Knoten n1 oder n2 ist der Stamm, die LCA ist die Wurzel . [3] Nur n1 oder n2 befindet sich in der Baumstruktur, LCA ist entweder der Wurzelknoten des linken Teilbaums der Baumwurzel oder die LCA ist der Wurzelknoten der rechten Teilbaum der Baumwurzel.

[4] Weder n1 noch n2 sind im Baum, es gibt keine LCA . [5] Sowohl n1 als auch n2 liegen in einer geraden Linie nebeneinander, LCA ist entweder n1 oder n2, die sich immer an der Wurzel des Baumes befinden.

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

Gehen Sie einfach von der root des gesamten Baums nach unten, solange sich beide angegebenen Knoten, beispielsweise p und q, für die Ancestor gefunden werden muss, im selben Unterbaum befinden (was bedeutet, dass ihre Werte beide kleiner oder größer als der von root sind). 

Dies geht direkt von der Wurzel zum Least Common Ancestor, ohne auf den Rest des Baums zu blicken. Es ist also fast so schnell wie es nur geht. Ein paar Möglichkeiten, dies zu tun.

Iterativ, O(1)

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 (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);
}
2
Rajnish

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

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 benötigten Bits, um x & y darzustellen, wobei die binäre Suche O ist (log (32)).
  2. das gemeinsame Präfix der binären Schreibweise von x und y ist der gemeinsame Vorfahr
  3. was immer durch 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 und y
  5. finden Sie Bits, die das verbleibende Suffix darstellen
  6. verschiebe x oder y um Suffix-Bits, um ein gemeinsames Präfix zu erhalten, das den gemeinsamen Vorfahren darstellt.

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

1
coder hacker
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
}

In Scala lautet der Code:

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
}
}
1
Jatin

Betrachten Sie diesen Baum enter image description here

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 postorder haben wir => 9,14,15,13,12,7 nach 8 & 11... in vorbestellung haben wir => 7,3,1,0,2,6,4,5,12,9 vor 8 & 11

9 ist die erste allgemeine Zahl, die nach 8 und 11 in der Postorder-Reihenfolge und vor 8 & 11 in der Vororder-Reihenfolge auftritt. Daher ist 9 die Antwort

  • zB: 2

Am wenigsten gemeinsamer Vorfahre von 5,10

11,9,14,15,13,12,7 in postorder 7,3,1,0,2,6,4 in vorbestellung

7 ist die erste Zahl, die nach 5,10 in der Nachordnung und vor 5,10 in der Vorordnung auftritt. Daher ist 7 die Antwort

1
nnc

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;
}
0
shubhamv
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;
    }
0
HeadAndTail

Lösung 1: Rekursiv - Schneller

  • Die Idee ist, den Baum von der Wurzel aus zu durchqueren. Wenn einer der angegebenen Schlüssel p und q mit root übereinstimmt, ist root LCA, vorausgesetzt, dass beide Schlüssel vorhanden sind. Wenn root mit keiner der Tasten übereinstimmt, können Sie für den linken und den rechten Teilbaum rekursieren. 
  • Der Knoten, bei dem ein Schlüssel in seinem linken Teilbaum vorhanden ist und der andere Schlüssel im rechten Teilbaum vorhanden ist, ist die LCA. Wenn beide Tasten im linken Teilbaum liegen, hat der linke Teilbaum auch LCA, ansonsten liegt LCA im rechten Teilbaum.
  • Zeitkomplexität: O (n)
  • Space Complexity: O(h) - für rekursive 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 - Übergeordnete Zeiger verwenden - Langsamer

  • Erstellen Sie eine leere Hashtabelle.
  • Fügen Sie p und alle seine Vorfahren in die Hash-Tabelle ein.
  • Prü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ären Baums.
  • Space Complexity: O(n) - Der für die übergeordnete Zeiger verwendete Hashtabelle, ancestor_set und queue, wäre 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;
    }
}
0
Pratik Patil

Code für A Breadth First Suchen Sie nach, ob sich beide Knoten im Baum befinden Fahren Sie dann mit der LCA-Suche fort Wenn Sie Verbesserungsvorschläge haben, __ Sie besuchten sie und beginnen die Suche an einem bestimmten Punkt, an dem wir aufgehört hatten, um den zweiten Knoten zu verbessern (falls er nicht BESUCHT gefunden wurde)

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;
}
}
0
Neelesh Salian

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

 Untersuchen Sie den Wurzelknoten 

 Wenn Wert1 und Wert2 strikt unter dem Wert am Stammknoten .__ liegen. Untersuchen Sie die linke Teilstruktur 
 Wenn nicht, sind Wert1 und Wert2 strikt größer als der Wert am Stammknoten 
 Untersuche den rechten Teilbaum 
 Sonst 
 Wurzel zurückgeben 
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;
} 
0
user2182531

Das Folgende ist der schnellste Weg, um dies zu lösen . Raumkomplexität O(1), Zeitkomplexität O (n). Ob

Wenn für einen Knoten sowohl der linke als auch der rechte Wert nicht null ist, ist dieser Knoten Ihre Antwort (drittes "Wenn" von oben). Wenn wir iterieren, ob ein Wert gefunden wurde, müssen wir seine Nachkommen nicht suchen, da alle Werte eindeutig sind und vorhanden sein müssen. Geben Sie einfach den gefundenen Knoten zurück, der übereinstimmt. Wenn der Inhalt der linken und rechten Verzweigung eines Knotens null ist, wird null nach oben übertragen. Wenn die Rekursion der obersten Ebene erreicht ist und ein Zweig einen Wert zurückgibt, geben andere diesen Wert nicht weiter, wenn beide einen aktuellen Knoten zurückgeben, der nicht null ist. Wenn die Rekursion auf Stammebene mit einer Null und einer anderen nicht null erreicht wird, wird kein Nullwert zurückgegeben, da die Frage verspricht, dass der Wert existiert, muss er sich im untergeordneten Baum des gefundenen Knotens befinden, den wir nie durchlaufen haben.

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

enter image description here

0
sapy

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

  1. Rekursive Version des Suchens von LCA im Binärbaum (O (N) - da höchstens jeder Knoten besucht wird) (Hauptpunkt der Lösung ist LCA ist (a) ) Nur Knoten im Binärbaum, in dem sich beide Elemente befinden Jede Seite der Unterbäume (links und rechts) ist LCA. (b) Und es ist auch egal, welcher Knoten auf beiden Seiten vorhanden ist - zunächst habe ich versucht, diese Informationen zu behalten, und offensichtlich wird die rekursive Funktion so verwirrend als ich es merkte, wurde es sehr elegant.

  2. Das Durchsuchen beider Knoten (O (N)) und das Nachverfolgen von Pfaden (verwendet zusätzlichen Speicherplatz - so ist # 1 wahrscheinlich überlegen, auch wenn der Speicherplatz wahrscheinlich vernachlässigbar ist, wenn der binäre Baum gut ausbalanciert ist, da dann zusätzlicher Speicherbedarf entsteht O (log (N)). 

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

  3. Nur für die Fertigstellung (nicht bezogen auf Frage), LCA 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;
        }

wobei die private rekursive Version über folgende öffentliche Methode aufgerufen wird:

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

wobei FindNodeAndPath als definiert ist 

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);
            }
        }
0
Dreamer

Sie sind richtig, dass eine Lösung mit Traversal ohne Elternknoten die Zeitkomplexität O(n) erhöht. 

Traversal-Ansatz Angenommen, Sie suchen nach LCA für Knoten A und B. Der einfachste Ansatz besteht darin, zuerst den Pfad von Root nach A und dann den Pfad von Root nach B zu erhalten können Sie leicht über sie iterieren und den letzten gemeinsamen Knoten finden, den untersten gemeinsamen Vorfahren von A und B.

Rekursive Lösung Ein anderer Ansatz ist die Verwendung von Rekursion. Erstens können wir LCA sowohl vom linken als auch vom rechten Baum erhalten (falls vorhanden). Wenn entweder A oder B der Wurzelknoten ist, ist die Wurzel die LCA und wir geben nur die Wurzel zurück, die der Endpunkt der Rekursion ist. Wenn wir den Baum immer wieder in Unterbäume unterteilen, schlagen wir entweder A oder B an.

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

Check Niedrigster gemeinsamer Vorfahr für detaillierte Analyse und Lösung.

0
Mark

Bei einigen Lösungen wird davon ausgegangen, dass ein Verweis auf den Wurzelknoten vorhanden ist. Bei einigen wird davon ausgegangen, dass tree eine BST ist . Das Freigeben meiner Lösung mithilfe von Hashmap ohne Verweis auf den Knoten root. Der Tree 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
    }
0
janusfidel

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

  • Legen Sie einen Pfadvektor für den Knoten n1 an.

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

  • Ein Pfadvektor, der die gesetzten Knoten von diesem Knoten impliziert, würde durchlaufen, um den fraglichen Knoten zu erreichen.

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

Nachteile für diesen Ansatz:

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

Dies ist jedoch 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;       
    }
0
Sumit Trehan

Grobe weg:

  • An jedem Knoten
    • X = find, ob auf der linken Seite des Knotens eines der beiden Elemente n1, n2 vorhanden ist
    • Y = find, ob einer der beiden Bereiche n1, n2 auf der rechten Seite des Knotens vorhanden ist
      • wenn der Knoten selbst n1 || ist n2 können wir es zur Verallgemeinerung entweder links oder rechts nennen.
    • Wenn sowohl X als auch Y wahr sind, ist der Knoten die Zertifizierungsstelle

Das Problem bei der obigen Methode ist, dass wir das Suchen mehrmals durchführen, dh es besteht die Möglichkeit, dass jeder Knoten mehrmals durchlaufen wird. Wir können dieses Problem überwinden, wenn wir die Informationen aufzeichnen können, um dies nicht zu tun wieder verarbeiten (dynamische Programmierung denken). 

Anstatt jeden Knoten zu finden, halten wir fest, was bereits gefunden wurde. 

Besserer Weg:

  • Wir prüfen, ob für einen gegebenen Knoten left_set (das heißt, entweder n1 | n2 wurde im linken Teilbaum gefunden wurde) oder right_set in der Tiefe zuerst. (HINWEIS: Wir geben der Wurzel selbst die Eigenschaft, left_set zu sein, wenn es entweder n1 | n2 ist.)
  • Wenn sowohl left_set als auch right_set ist, ist der Knoten eine LCA.

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;
   }
}
0
Shatru Sadhu

Wenn jemand an Pseudo-Code interessiert ist (für Universitäts-Home-Werke), ist dies 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
0
Sameera R.

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), der Algorithmus funktioniert jedoch auch für einen Binärbaum. Die Idee ist, alle Knoten, die vom Knoten A bis zum Knoten B liegen, in der Reihenfolge durchzugehen, und die Indizes für diese in der Reihenfolge nach der Reihenfolge zu suchen. Der Knoten mit maximalem Index in der Reihenfolge nach der Reihenfolge ist der niedrigste gemeinsame Vorfahr. 

Dies ist ein funktionierender C-Code zum Implementieren einer Funktion, um den niedrigsten gemeinsamen Vorfahren in einem binären Baum zu finden. Ich stelle auch alle Hilfsfunktionen usw. zur Verfügung, gehe 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);


}
0
Gaurav Sinha

Hier ist was ich denke,

  1. Finden Sie die Route für den ersten Knoten und speichern Sie sie in arr1.
  2. Beginnen Sie, die Route für den 2-Knoten zu finden, und überprüfen Sie dabei jeden Wert von root bis arr1.
  3. zeit, wenn der Wert unterschiedlich ist, beenden. Alter übereinstimmender Wert ist die LCA.

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

0
badri.coder

Ich habe eine Lösung gefunden

  1. Nehmen Sie in Ordnung
  2. Vorbestellung übernehmen
  3. Postorder nehmen

Abhängig von 3 Durchläufen können Sie entscheiden, wer der LCA ist . Von LCA finden Sie die Entfernung beider Knoten . Fügen Sie diese beiden Entfernungen hinzu.

0
Rajdeep Sardar

Hier ist der Weg von C++. Ich habe versucht, den Algorithmus so verständlich 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)
  ...
0
iammilind