Comment trouver le plus petit ancêtre commun de deux nœuds dans n'importe quel arbre binaire?

187

L'arbre binaire ici n'est pas nécessairement un arbre de recherche binaire.
La structure pourrait être considérée comme -

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

La solution maximale que je pourrais trouver avec un ami était quelque chose de ce genre -
Considérez cet arbre binaire :

Arbre binaire

La traversée en ordre donne - 8, 4, 9, 2, 5, 1, 6, 3, 7

Et la traversée post-ordre donne - 8, 9, 4, 5, 2, 6, 7, 3, 1

Ainsi, par exemple, si nous voulons trouver l'ancêtre commun des nœuds 8 et 5, alors nous faisons une liste de tous les nœuds qui sont entre 8 et 5 dans le parcours d'arbre inorder, qui dans ce cas se trouve être [4, 9 , 2]. Ensuite, nous vérifions quel nœud de cette liste apparaît en dernier dans le parcours de post-ordre, qui est 2. Par conséquent, l'ancêtre commun pour 8 et 5 est 2.

La complexité de cet algorithme, je crois, est O (n) (O (n) pour les traversées en ordre / post-ordre, le reste des étapes étant à nouveau O (n) car ce ne sont rien de plus que de simples itérations dans des tableaux). Mais il y a de fortes chances que ce soit faux. :-)

Mais c'est une approche très grossière, et je ne suis pas sûr si cela échoue dans certains cas. Existe-t-il une autre solution (peut-être plus optimale) à ce problème?

Siddhant
la source
6
Par curiosité, quelle en est l'utilité pratique?
David Brunelle
19
@David: la réponse aux requêtes LCA est très utile. LCA + arbre de suffixes = puissants algorithmes liés aux chaînes.
44
Et quand j'ai posé une question similaire, elle a été rejetée avec des commentaires comme sa question d'entrevue. Dualité de SO? :(
some_other_guy
5
@Siddant +1 pour les détails donnés dans la question. :)
amod
5
@DavidBrunelle Une application pratique du calcul de l'ACV: c'est un calcul essentiel lors du rendu des pages Web, en particulier lors du calcul des feuilles de style en cascade (CSS) applicables à un élément DOM particulier.
zc22

Réponses:

74

Nick Johnson a raison de dire qu'un algorithme de complexité en temps O (n) est le meilleur que vous puissiez faire si vous n'avez pas de pointeurs parents.) Pour une version récursive simple de cet algorithme, voir le code dans l'article de Kinding qui s'exécute en temps O (n) .

Mais gardez à l'esprit que si vos nœuds ont des pointeurs parents, un algorithme amélioré est possible. Pour les deux nœuds en question, construisez une liste contenant le chemin de la racine au nœud en commençant au nœud, puis en insérant le parent.

Donc, pour 8 dans votre exemple, vous obtenez (montrant les étapes): {4}, {2, 4}, {1, 2, 4}

Faites de même pour votre autre nœud en question, ce qui entraîne (étapes non illustrées): {1, 2}

Maintenant, comparez les deux listes que vous avez faites en recherchant le premier élément où la liste diffère, ou le dernier élément d'une des listes, selon la première éventualité.

Cet algorithme nécessite un temps O (h) où h est la hauteur de l'arbre. Dans le pire des cas, O (h) équivaut à O (n), mais si l'arbre est équilibré, c'est seulement O (log (n)). Il nécessite également un espace O (h). Une version améliorée est possible qui n'utilise que l'espace constant, avec le code affiché dans l' article du CEGRD


Indépendamment de la façon dont l'arbre est construit, s'il s'agit d'une opération que vous effectuez plusieurs fois sur l'arbre sans le changer entre les deux, il existe d'autres algorithmes que vous pouvez utiliser qui nécessitent une préparation de temps O (n) [linéaire], mais en trouvant ensuite paire ne prend que le temps O (1) [constant]. Pour obtenir des références à ces algorithmes, consultez la page sur les problèmes d'ancêtres communs les plus bas sur Wikipedia . (Merci à Jason d'avoir publié ce lien à l'origine)

Kevin Cathcart
la source
1
Cela fait le travail si le pointeur parent est donné. Les nœuds dans l'arborescence sont comme la structure que j'ai donnée dans ma question - juste les pointeurs enfants gauche / droite, pas de pointeur parent. Existe-t-il une solution O (log (n)) s'il n'y a pas de pointeur parent disponible et que l'arbre n'est pas un arbre de recherche binaire, et n'est qu'un arbre binaire?
Siddhant
2
Si vous n'avez pas de moyen particulier de trouver le chemin entre le parent et un nœud donné, alors il faudra en moyenne O (n) temps pour le trouver. Cela rendra impossible d'avoir le temps O (log (n)). Cependant, le coût unique O (n), avec la recherche de paires O (1), peut être votre meilleur pari de toute façon si vous deviez effectuer cette opération plusieurs fois sans changer l'arbre entre les deux. Sinon, si possible, vous devez ajouter le pointeur parent. Cela peut accélérer plusieurs algorithmes potentiels, mais je suis presque sûr que cela ne change pas l'ordre des algorithmes existants. J'espère que cela t'aides.
Kevin Cathcart
1
cette approche peut être réalisée en utilisant la mémoire O (1) - voir la solution d'Artelius (et autres) sur stackoverflow.com/questions/1594061/…
Tom Sirgedas
@Tom: En effet, cela fonctionnerait pour limiter la complexité de la mémoire à O (1) pour l'algorithme basé sur une liste. Évidemment, cela signifie une itération dans l'arbre lui-même une fois pour chaque côté pour obtenir la profondeur des nœuds, puis une deuxième fois (partielle) pour trouver l'ancêtre commun. Le temps O (h) et l'espace O (1) sont clairement optimaux pour le cas d'avoir des pointeurs parents, et de ne pas faire de précalcul O (n).
Kevin Cathcart
1
@ALBI O(h)n'est que O(log(n))si l'arbre est équilibré. Pour n'importe quel arbre, qu'il soit binaire ou non, si vous avez des pointeurs parents, vous pouvez déterminer le chemin d'une feuille à la racine dans le O(h)temps, simplement en suivant le pointeur parent jusqu'à des hheures. Cela vous donne le chemin de la feuille à la racine. Si les chemins sont stockés sous forme de pile, l'itération de la pile vous donne le chemin de la racine à la feuille. Si vous n'avez pas de pointeurs parents et que vous n'avez pas de structure spéciale pour l'arborescence, trouver le chemin de la racine à la feuille prend du O(n)temps.
Kevin Cathcart
108

En partant du rootnœud et en descendant si vous trouvez un nœud qui a l'un pou l' autre qcomme enfant direct, c'est l'ACV. (modifier - cela devrait être si pou qest la valeur du nœud, renvoyez-le. Sinon, cela échouera lorsque l'un de pou qest un enfant direct de l'autre.)

Sinon, si vous trouvez un nœud avec pdans son sous-arbre droit (ou gauche) et qdans son sous-arbre gauche (ou droit), il s'agit de l'ACV.

Le code fixe ressemble à:

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

Le code ci-dessous échoue lorsque l'un est l'enfant direct de l'autre.

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 en action

codaddict
la source
2
solution élégante, mais la racine == p || root == q => le bit racine de retour semble trop optimiste. Et s'il s'avère que la racine est p / q, mais que l'autre nœud recherché n'est pas réellement dans l'arbre?
Ian Durkan
15
Je suppose que ce code échoue lorsque p ou q est une valeur qui n'est pas dans l'arbre binaire. Ai-je raison? Par exemple LCA (8,20). votre code renvoie 8. mais 20 n'est pas présent dans l'arbre binaire
javaMan
3
Quel est le coût de cette solution? Est-ce efficace? Il semble continuer à chercher même après avoir trouvé à la fois p et q. Est-ce à cause de la possibilité que p et q ne soient pas uniques dans l'arborescence car ce n'est pas un BST et peut contenir des doublons?
MikeB
3
@MikeB, cette solution est définitivement O (n), car vous ne traversez chaque nœud qu'une seule fois dans le pire des cas. Peter Lee, c'est le plus efficace que vous puissiez faire sans utiliser de pointeurs parents. Avez-vous une meilleure solution?
gsingh2011
8
la première solution imparfaite doit être supprimée pour ne pas gêner
Zinan Xing
50

Voici le code de travail en 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; 
}
Akash Verma
la source
4
Cela ne fonctionne pas lorsqu'un nœud n'existe pas dans l'arborescence.
Pratik Khadloya
optimiseriez-vous votre code si l'arbre donné est un BST?
Mona Jalal
1
"Si la racine est l'une de a ou b, alors c'est l'ACV." cela pourrait ne pas être vrai. Ce que vous savez à ce stade, c'est que vous n'avez pas besoin de vérifier l'un de ses enfants pour trouver l'ACV. Cela se produit parce que nous pouvons vérifier plus tard si pour le parent de root, il y avait des correspondances sur les deux branches (LCA est le parent) ou juste l'une d'entre elles (dans ce cas, celui-ci pourrait être le LCA, ou un ancêtre encore plus grand pourrait être le LCA ).
andresp
28

Les réponses données jusqu'à présent utilisent la récursivité ou stockent, par exemple, un chemin en mémoire.

Ces deux approches peuvent échouer si vous avez un arbre très profond.

Voici mon point de vue sur cette question. Lorsque nous vérifions la profondeur (distance de la racine) des deux nœuds, s'ils sont égaux, nous pouvons alors remonter en toute sécurité des deux nœuds vers l'ancêtre commun. Si l'une des profondeurs est plus grande, nous devrions remonter du nœud le plus profond tout en restant dans l'autre.

Voici le 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;    

La complexité temporelle de cet algorithme est: O (n). La complexité spatiale de cet algorithme est: O (1).

En ce qui concerne le calcul de la profondeur, nous pouvons d'abord nous souvenir de la définition: Si v est racine, profondeur (v) = 0; Sinon, profondeur (v) = profondeur (parent (v)) + 1. Nous pouvons calculer la profondeur comme suit:

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;
CEGRD
la source
6
Les arbres binaires n'ont généralement pas de référence à l'élément parent. L'ajout d'une référence parent peut être fait sans aucun problème, mais je considérerais que l'espace auxiliaire O (n).
John Kurlak
Il y a une hypothèse subtile dans cette solution. Si un nœud est un parent direct ou indirect de l'autre (c'est-à-dire que le nœud le plus profond est dans un arbre enraciné au nœud le moins profond), cette solution renvoie le parent du nœud le moins profond comme résultat. Selon la façon dont vous définissez le plus petit ancêtre commun, ce n'est peut-être pas ce que vous voulez. Certaines définitions exigeront que le nœud le moins profond soit lui-même le parent. Dans ce cas, vous devrez suivre quel est le nœud le moins profond et le renvoyer.
Srikanth
8

Eh bien, cela dépend de la structure de votre arbre binaire. Vraisemblablement, vous avez un moyen de trouver le nœud feuille souhaité en fonction de la racine de l'arbre - appliquez-le simplement aux deux valeurs jusqu'à ce que les branches que vous choisissez divergent.

Si vous ne disposez pas d'un moyen de trouver la feuille souhaitée à partir de la racine, alors votre seule solution - à la fois en fonctionnement normal et pour trouver le dernier nœud commun - est une recherche par force brute de l'arbre.

Nick Johnson
la source
8

Cela peut être trouvé à: - 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;
        }
    }
}
Baban
la source
pouvez-vous s'il vous plaît me dire comment votre code se comportera si p est présent mais q n'est pas du tout présent dans l'arbre? De même, p et q ne sont pas présents. Merci!!!
Essai le
Quel est le grand O en termes de temps? Je pense que c'est O (n * log (n)), deux lent.
Peter Lee
6

Pour découvrir l'ancêtre commun de deux nœuds: -

  • Trouvez le nœud donné Node1 dans l'arborescence à l'aide de la recherche binaire et enregistrez tous les nœuds visités dans ce processus dans un tableau, par exemple A1. Heure - O (logn), Espace - O (logn)
  • Trouvez le Node2 donné dans l'arborescence à l'aide de la recherche binaire et enregistrez tous les nœuds visités dans ce processus dans un tableau, par exemple A2. Heure - O (logn), Espace - O (logn)
  • Si la liste A1 ou la liste A2 est vide, alors un nœud n'existe pas donc il n'y a pas d'ancêtre commun.
  • Si la liste A1 et la liste A2 ne sont pas vides, regardez dans la liste jusqu'à ce que vous trouviez un nœud non correspondant. Dès que vous trouvez un tel nœud, le nœud antérieur est un ancêtre commun.

Cela fonctionnerait pour l'arbre de recherche binaire.

Vipin
la source
2
Il a clairement déclaré que l'arbre n'était PAS nécessairement un BST.
Peter Lee
@Peter Lee - La logique ci-dessus fonctionnerait même pour n'importe quel arbre binaire avec un simple changement. Au lieu d'une recherche binaire de nœuds donnés, appliquez une recherche linéaire (c'est-à-dire n'importe quelle traversée mais devrait être la même dans les deux cas). Hors cours d'exécution serait O (n) au lieu de O (logn). En fait, cet algorithme est le plus robuste lorsque le pointeur parent n'est pas disponible. L'algorithme rucursif donné par beaucoup (à savoir 'codaddict') ne fonctionnera pas quand l'un des nœuds donnés n'appartient pas à l'arbre)
KGhatak
3

L'algorithme récursif ci-dessous fonctionnera en O (log N) pour un arbre binaire équilibré. Si l'un des nœuds passés dans la fonction getLCA () est le même que la racine, la racine sera l'ACV et il ne sera pas nécessaire d'effectuer une recussrion.

Cas de test. [1] Les deux nœuds n1 et n2 sont dans l'arborescence et résident de chaque côté de leur nœud parent. [2] Le nœud n1 ou n2 est la racine, le LCA est la racine. [3] Seul n1 ou n2 est dans l'arborescence, LCA sera soit le nœud racine du sous-arbre gauche de la racine de l'arbre, soit l'ACV sera le nœud racine du sous-arbre droit de la racine de l'arbre.

[4] Ni n1 ni n2 ne sont dans l'arborescence, il n'y a pas de LCA. [5] Les deux n1 et n2 sont en ligne droite l'un à côté de l'autre, LCA sera soit de n1 ou n2 qui se rapproche jamais de la racine de l'arbre.

//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);
}
gilla07
la source
3

Il suffit de descendre de l'arbre entier roottant que les deux nœuds donnés, disons pet q, pour lesquels l'ancêtre doit être trouvé, sont dans le même sous-arbre (ce qui signifie que leurs valeurs sont à la fois plus petites ou plus grandes que celles de racine).

Cela va directement de la racine à l'ancêtre le moins commun, sans regarder le reste de l'arbre, donc c'est à peu près aussi rapide que possible. Quelques façons de le faire.

Itératif, espace 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;
}

en cas de débordement, je ferais (root.val - (long) p.val) * (root.val - (long) q.val)

Récursif

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);
}
Rajnish
la source
2
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
}
Krishnachandra Sharma
la source
2

Considérez cet arbre entrez la description de l'image ici

Si nous effectuons une traversée de post-ordre et de pré-ordre et trouvons le premier prédécesseur et successeur commun, nous obtenons l'ancêtre commun.

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

  • par exemple: 1

Ancêtre le moins commun de 8,11

en postorder nous avons => 9,14,15,13,12,7 après 8 & 11 en précommande nous avons => 7,3,1,0,2,6,4,5,12,9 avant 8 & 11

9 est le premier nombre courant qui apparaît après 8 et 11 en post-commande et avant 8 et 11 en précommande, donc 9 est la réponse

  • par exemple: 2

Ancêtre le moins commun de 5,10

11,9,14,15,13,12,7 en post-commande 7,3,1,0,2,6,4 en précommande

7 est le premier nombre qui apparaît après 5,10 en post-commande et avant 5,10 en précommande, donc 7 est la réponse

nnc
la source
2

S'il s'agit d'un arbre binaire complet avec des enfants du nœud x comme 2 * x et 2 * x + 1, il existe un moyen plus rapide de le faire

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

Comment ça marche

  1. obtenir les bits nécessaires pour représenter x & y qui en utilisant la recherche binaire est O (log (32))
  2. le préfixe commun de la notation binaire de x & y est l'ancêtre commun
  3. celui qui est représenté par le plus grand nombre de bits est amené au même bit par k >> diff
  4. k = x ^ y efface le préfixe commun de x & y
  5. trouver des bits représentant le suffixe restant
  6. décalez x ou y par bits de suffixe pour obtenir le préfixe commun qui est l'ancêtre commun.

Cela fonctionne parce que fondamentalement, divisez le plus grand nombre par deux récursivement jusqu'à ce que les deux nombres soient égaux. Ce nombre est l'ancêtre commun. La division est effectivement la bonne opération de changement de vitesse. Nous devons donc trouver le préfixe commun de deux nombres pour trouver l'ancêtre le plus proche

codeur hacker
la source
2

Dans scala, vous pouvez:

  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
    }
  }
Jatin
la source
1
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;
    }
HeadAndTail
la source
0

Voici la manière C ++ de le faire. J'ai essayé de garder l'algorithme aussi simple que possible à comprendre:

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

Comment l'utiliser:

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

Le moyen le plus simple de trouver l'ancêtre commun le plus bas consiste à utiliser l'algorithme suivant:

Examiner le nœud racine

si valeur1 et valeur2 sont strictement inférieures à la valeur au nœud racine 
    Examiner le sous-arbre gauche
sinon si valeur1 et valeur2 sont strictement supérieures à la valeur au nœud racine 
    Examiner le sous-arbre droit
autre
    retourner la racine
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;
} 
user2182531
la source
6
Ce n'est PAS un BST!
Peter Lee
0

J'ai trouvé une solution

  1. Prendre en ordre
  2. Prenez la précommande
  3. Prendre la commande

En fonction de 3 parcours, vous pouvez décider qui est le LCA. À partir de LCA, trouvez la distance des deux nœuds. Ajoutez ces deux distances, qui est la réponse.

Rajdeep Sardar
la source
0

Voici ce que je pense,

  1. Trouvez l'itinéraire pour le premier nœud, enregistrez-le sur arr1.
  2. Commencez à trouver l'itinéraire pour le nœud 2, tout en vérifiant chaque valeur de la racine à arr1.
  3. moment où la valeur diffère, quittez. L'ancienne valeur correspondante est l'ACV.

Complexité: étape 1: O (n), étape 2 = ~ O (n), total = ~ O (n).

badri.coder
la source
0

Voici deux approches en c # (.net) (toutes deux discutées ci-dessus) pour référence:

  1. Version récursive de la recherche de LCA dans l'arbre binaire (O (N) - car au plus chaque nœud est visité) (les principaux points de la solution est LCA est (a) le seul nœud de l'arbre binaire où les deux éléments résident de chaque côté des sous-arbres (à gauche et à droite) est LCA. (b) Et aussi peu importe quel nœud est présent de chaque côté - au départ j'ai essayé de garder cette information, et évidemment la fonction récursive est devenue si déroutante.Une fois que je l'ai réalisée, elle est devenue très élégante.

  2. La recherche des deux nœuds (O (N)) et le suivi des chemins (utilise de l'espace supplémentaire - donc, # 1 est probablement supérieur même si l'espace est probablement négligeable si l'arbre binaire est bien équilibré, car la consommation de mémoire supplémentaire sera juste en O (log (N)).

    de sorte que les chemins sont comparés (essentiellement similaire à la réponse acceptée - mais les chemins sont calculés en supposant que le nœud de pointeur n'est pas présent dans le nœud de l'arbre binaire)

  3. Juste pour compléter ( sans rapport avec la question ), LCA en BST (O (log (N))

  4. Des tests

Récursif:

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

où ci-dessus la version récursive privée est appelée par la méthode publique suivante:

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

Solution en gardant une trace des chemins des deux nœuds:

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

où FindNodeAndPath est défini comme

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) - non lié (juste pour compléter pour référence)

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

Tests unitaires

[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);
            }
        }
Rêveur
la source
0

Si quelqu'un s'intéresse au pseudo code (pour les travaux universitaires à domicile), en voici un.

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
Sameera R.
la source
0

Bien que cela ait déjà été répondu, c'est mon approche de ce problème en utilisant le langage de programmation C. Bien que le code montre un arbre de recherche binaire (en ce qui concerne insert ()), mais l'algorithme fonctionne également pour un arbre binaire. L'idée est de passer en revue tous les nœuds qui se trouvent du nœud A au nœud B dans un parcours en ordre, de rechercher les indices pour ceux-ci dans le parcours de post-ordre. Le nœud avec l'index maximum dans le parcours post-ordre est le plus petit ancêtre commun.

Il s'agit d'un code C fonctionnel pour implémenter une fonction pour trouver le plus petit ancêtre commun dans un arbre binaire. Je propose également toutes les fonctions utilitaires, etc., mais passez à CommonAncestor () pour une compréhension rapide.

#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);


}
SeattleOrBayArea
la source
0

Il peut y avoir une autre approche. Cependant, il n'est pas aussi efficace que celui déjà suggéré dans les réponses.

  • Créez un vecteur de chemin pour le nœud n1.

  • Créez un deuxième vecteur de chemin pour le nœud n2.

  • Vecteur de chemin impliquant l'ensemble des nœuds de celui-ci traverser pour atteindre le nœud en question.

  • Comparez les deux vecteurs de chemin. L'index où ils ne correspondent pas, retourne le nœud à cet index - 1. Cela donnerait l'ACV.

Inconvénients de cette approche:

Besoin de parcourir l'arbre deux fois pour calculer les vecteurs de chemin. Besoin d'espace O (h) supplémentaire pour stocker les vecteurs de chemin.

Cependant, cela est également facile à mettre en œuvre et à comprendre.

Code de calcul du vecteur de chemin:

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;       
    }
Sumit Trehan
la source
0

Essayez comme ça

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;
}
Shubhamv
la source
0

Manière brute:

  • À chaque nœud
    • X = trouver si l'un des n1, n2 existe sur le côté gauche du nœud
    • Y = trouver si l'un des n1, n2 existe sur le côté droit du nœud
      • si le nœud lui-même est n1 || n2, nous pouvons l'appeler trouvé à gauche ou à droite à des fins de généralisation.
    • Si X et Y sont tous les deux vrais, alors le nœud est l'autorité de certification

Le problème avec la méthode ci-dessus est que nous allons faire la "recherche" plusieurs fois, c'est-à-dire qu'il y a une possibilité que chaque nœud soit traversé plusieurs fois. Nous pouvons surmonter ce problème si nous pouvons enregistrer les informations afin de ne pas les traiter à nouveau (pensez à la programmation dynamique).

Ainsi, plutôt que de rechercher chaque nœud, nous gardons une trace de ce qui a déjà été trouvé.

Meilleure façon:

  • Nous vérifions si pour un nœud donné si left_set (ce qui signifie que n1 | n2 a été trouvé dans le sous-arbre de gauche) ou right_set en profondeur d'abord. (NOTE: Nous donnons à la racine elle-même la propriété d'être left_set si c'est soit n1 | n2)
  • Si à la fois left_set et right_set, le nœud est un 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;
   }
}
Shatru Sadhu
la source
0

Code pour A Breadth First Search pour vous assurer que les deux nœuds sont dans l'arborescence. Alors seulement, avancez avec la recherche LCA. Veuillez commenter si vous avez des suggestions à améliorer. Je pense que nous pouvons probablement les marquer comme visités et redémarrer la recherche à un certain point où nous nous sommes arrêtés pour améliorer le deuxième nœud (s'il n'est pas trouvé VISITÉ)

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

Vous avez raison de dire que sans nœud parent, une solution avec traversée vous donnera une complexité en temps O (n).

Approche transversale transversale Supposons que vous trouviez l'ACV pour les nœuds A et B, l'approche la plus simple consiste d'abord à obtenir le chemin de la racine à A, puis à obtenir le chemin de la racine à B.Une fois que vous avez ces deux chemins, vous pouvez facilement les parcourir. et trouvez le dernier nœud commun, qui est le plus petit ancêtre commun de A et B.

Solution récursive Une autre approche consiste à utiliser la récursivité. Tout d'abord, nous pouvons obtenir LCA à la fois de l'arbre gauche et de l'arbre droit (s'il existe). Si l'un de A ou B est le nœud racine, alors la racine est l'ACV et nous renvoyons simplement la racine, qui est le point final de la récursivité. Au fur et à mesure que nous divisons l'arbre en sous-arbres, nous atteindrons finalement A et B.

Pour combiner des solutions de sous-problèmes, si LCA (arbre de gauche) renvoie un nœud, nous savons que A et B se situent dans l'arbre de gauche et le nœud retourné est le résultat final. Si LCA (gauche) et LCA (droite) renvoient des nœuds non vides, cela signifie que A et B sont respectivement dans l'arborescence gauche et droite. Dans ce cas, le nœud racine est le nœud commun le plus bas.

Vérifiez le plus petit ancêtre commun pour une analyse détaillée et une solution.

marque
la source
0

Certaines des solutions ici supposent qu'il existe une référence au nœud racine, d'autres supposent que l'arbre est un BST. Partager ma solution en utilisant hashmap, sans référence au rootnœud et à l'arborescence peut être BST ou non-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
    }
janusfidel
la source
0

Solution 1: récursif - plus rapide

  • L'idée est de parcourir l'arbre à partir de la racine. Si l'une des clés p et q données correspond à root, alors root est LCA, en supposant que les deux clés sont présentes. Si root ne correspond à aucune des clés, nous recurse pour le sous-arbre gauche et droit.
  • Le nœud qui a une clé présente dans son sous-arbre gauche et l'autre clé présente dans le sous-arbre droit est le LCA. Si les deux clés se trouvent dans le sous-arbre gauche, alors le sous-arbre gauche a également LCA, sinon LCA se trouve dans le sous-arbre droit.
  • Complexité temporelle: O (n)
  • Complexité spatiale: O (h) - pour la pile d'appels récursifs
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)
    }
}

Solution 2: Itérative - Utilisation des pointeurs parents - Plus lente

  • Créez une table de hachage vide.
  • Insérez p et tous ses ancêtres dans la table de hachage.
  • Vérifiez si q ou l'un de ses ancêtres existe dans la table de hachage, si oui, retournez le premier ancêtre existant.
  • Complexité temporelle: O (n) - Dans le pire des cas, nous pourrions visiter tous les nœuds de l'arbre binaire.
  • Complexité de l'espace: O (n) - L'espace utilisé le pointeur parent Hash-table, ancestor_set et queue, serait O (n) chacun.
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;
    }
}
Pratik Patil
la source