Kaip rasti bet kokį dvejetainį medį mažiausio dviejų mazgų protėvių?

Čia dvejetainis medis nebūtinai gali būti dvejetainis paieškos medis.
Struktūra gali būti laikoma -

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

Didžiausias sprendimas, kurį galėčiau nuspręsti su draugu, buvo kažkas panašaus -
Apsvarstykite šį dvejetainį medį :

Dvejetainis medis http://lcm.csa.iisc.ernet.in/dsa/img151.gif

Kryžminis kelias - 8, 4, 9, 2, 5, 1, 6, 3, 7

Ir po žiedinės sankryžos, mes gauname 8, 9, 4, 5, 2, 6, 7, 3, 1

Pavyzdžiui, jei norime rasti bendrą mazgų 8 ir 5 protėvį, tada sudarysime visų mazgų, kurie yra tarp 8 ir 5, apeinant medžio medį, kuris šiuo atveju yra [4, 9, 2], sąrašas. Tada mes patikriname, kuris sąraše esantis mazgas yra paskutinioji problema po siuntimo, kuris yra 2. Todėl 8 ir 5 bendras protėvis yra 2.

Manau, kad šio algoritmo sudėtingumas yra O (n) (O (n), kai viduje yra pasienio / posistemio aplinkkeliai, kiti veiksmai yra O (n) dar kartą, nes jie yra tik paprastos iteracijos masyvuose). Tačiau yra didelė tikimybė, kad ji neteisinga: -)

Tačiau tai yra labai apytikris požiūris, ir aš nesu įsitikinęs, kad ji tam tikra proga suskaidys. Ar yra dar vienas (galbūt labiau optimalus) šios problemos sprendimas?

174
28 сент. nustatė Siddhant 28 rugsėjis 2009-09-28 00:01 '09 - 0:01 2009-09-28 00:01
@ 32 atsakymai
  • 1
  • 2

Nickas Johnsonas yra teisus, kad O (n) laiko sudėtingumo algoritmas yra geriausias dalykas, kurį galite padaryti, jei neturite tėvų.) Paprastai šios algoritmo rekursijos versijos ieškokite kodo Kinding pranešime, kuris veikia O (n) laiku ,

Tačiau nepamirškite, kad jei jūsų mazgai turi tėvų rodmenis, galimas patobulintas algoritmas. Sukurkite abiejų atitinkamų mazgų sąrašą, kuriame yra kelias nuo šaknies iki mazgo, pradedant mazgo ir patronuojančios dalies priekiniu įdėjimu.

Taigi, 8 pavyzdys jūsų pavyzdyje: (rodyti veiksmus): {4}, {2, 4}, {1, 2, 4}

Atlikite tą patį ir kitame mazge, todėl (nepateikiami veiksmai): {1, 2}

Dabar palyginkite du atliktus sąrašus, ieškodami pirmojo elemento, kuriame sąrašas yra kitoks, arba paskutinį elementą viename iš sąrašų, priklausomai nuo to, kas įvyksta anksčiau.

Šiam algoritmui reikia O (h) laiko, kai h yra medžio aukštis. Blogiausiu atveju O (h) yra lygiavertis O (n), bet jei medis yra subalansuotas, tai tik O (log (n)). Ji taip pat reikalauja O (h) vietos. Galima patobulinta versija, kurioje naudojama tik nuolatinė erdvė, o kodas rodomas CEGRD pranešime


Nepriklausomai nuo to, kaip medis yra pastatytas, jei tai yra veiksmas, kurį atliekate daug kartų medyje nekeičiant jų tarp jų, yra ir kitų algoritmų, kuriuos galite naudoti, todėl reikia laiko O (n) [linijinis], bet tada bet kurios poros paieška užtrunka tik O (1) [pastovus] laikas. Nuorodoms į šiuos algoritmus žr. Problemos puslapį, kuriame yra mažiausias bendrasis protėvis Vikipedijoje . (Kredituokite „Jason“ už pirmą šios nuorodos paskelbimą)

67
28 сент. atsakymą pateikė Kevin Cathcart, rugsėjo 28 d 2009-09-28 02:43 '09 2:43 am 2009-09-28 02:43

Pradedant nuo root mazgo ir judant žemyn, jei randate bet kurį mazgo, kuris yra tiesioginis vaikas p arba q , tai yra LCA. (redaguoti - tai turėtų būti, jei p arba q yra mazgo vertė, grąžinkite jį. Priešingu atveju, jis nepavyks, jei vienas iš p arba q yra tiesioginis kito palikuonis.)

Jei surasite mazą su p dešinėje (arba kairėje) subtree ir q kairėje (arba dešinėje) subtree, tai yra LCA.

Fiksuotas kodas atrodo taip:

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

Žemiau nurodytas kodas nepavyksta, jei vienas iš jų yra tiesioginis kito palikuonis.

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

Veikimo kodas

101
15 февр. atsakymas pateikiamas koduotu adresu : vasario 15 d. 2011-02-15 09:55 '11 at 9:55 2011-02-15 09:55

Čia yra darbinis kodas Java

46
28 янв. atsakymą pateikė „ Akash Verma“ sausio 28 d. 2012-01-28 18:15 '12, 18:15, 2012-01-28 18:15

Šie atsakymai naudoja rekursiją arba saugojimą, pavyzdžiui, atminties kelią.

Abu šie metodai gali nepavykti, jei turite labai gilų medį.

Čia yra mano klausimas šiuo klausimu. Kai tikriname abiejų mazgų gylį (atstumą nuo šaknų), jei jie yra lygūs, tada galime saugiai judėti iš abiejų mazgų į bendrą protėvį. Jei vienas iš gylio yra didesnis, turime judėti aukštyn nuo gilesnio mazgo, likdami kitame.

Čia yra kodas:

 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; 

Šio algoritmo laiko sudėtingumas yra: O (n). Šio algoritmo sudėtingumas yra toks: O (1).

Kalbant apie gylį, pirmiausia galime prisiminti apibrėžimą: Jei v yra šaknis, gylis (v) = 0; Priešingu atveju, gylis (v) = gylis (tėvų (v)) + 1. Gylį galima apskaičiuoti taip:

 depth(v): int d = 0; vv = v; while ( vv is not root ) { vv = parent(vv); d++; } return d; 
25
31 мая '11 в 7:40 2011-05-31 07:40 CEGRD atsakymas yra gegužės 31 d., 11 val., 07:40, 2011-05-31 07:40

Tai galima rasti: - 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
17 мая '10 в 20:58 2010-05-17 20:58 Babano atsakymas gegužės 17 d. 10 val. 20:58 2010-05-17 20:58

Na, tai priklauso nuo to, kaip struktūrizuotas jūsų dvejetainis medis. Manoma, kad jūs galite rasti norimą mazgo lapą medžio šaknies atžvilgiu - tiesiog pritaikykite jį abiem vertėms, kol pasirinktos šakos skiriasi.

Jei neturite jokio būdo rasti teisingą lapą, kurį suteikia šaknis, tuomet jūsų vienintelis sprendimas, tiek normalaus veikimo metu, tiek ieškant paskutinio bendro mazgo, yra ieškoti medžio jėgos.

7
28 сент. Nick Johnson atsakymas, rugsėjo 28 d 2009-09-28 00:47 '09 ne 0:47 2009-09-28 00:47

Norėdami sužinoti bendrą dviejų mazgų protėvį:

  • Suraskite nurodytą mazgo mazgo1 medyje naudodami dvejetainę paiešką ir išsaugokite visus šiame procese aplankytus mazgus, pvz., A1 masyvu. Laikas - O (logn), tarpas - O (logn)
  • Raskite šį mazgelį medyje naudodami dvejetainę paiešką ir išsaugokite visus šiame procese aplankytus mazgus, pvz., A2 masyvu. Laikas - O (logn), tarpas - O (logn)
  • Jei A1 arba A2 sąrašas yra tuščias, tada mazgas neegzistuoja, todėl nėra bendro protėvio.
  • Jei A1 sąrašo ir A2 sąrašo nėra, peržiūrėkite sąrašą, kol surasite neteisingą mazgą. Kai surasite tokį mazgą, tada susikurkite, kol jis yra bendras protėvis.

Tai veiks dvejetainiai paieškos medžiai.

5
04 янв. Atsakymas pateikiamas Vipin 04 Jan. 2011-01-04 18:55 '11 at 18:55 2011-01-04 18:55

Tarkhan algoritmas su mažiausiu Tarjano protėvių plitimu yra pakankamai geras (taip pat žr. Vikipediją ). Išsamesnė problema (mažiausia bendra protėvių problema) Vikipedijoje .

5
28 сент. Jono atsakymas 2009-09-28 00:06 '09 - 0:06 2009-09-28 00:06

Bandžiau pateikti iliustracinius vaizdus ir veikiau „Java“ kodą,

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

3
10 февр. Bragboy atsakymas, vasario 10 d 2010-02-10 16:44 '10, 4:44, 2010-02-10 16:44

Žemiau, rekursinis algoritmas veiks O (log N), kad būtų subalansuotas dvejetainis medis. Jei bet kuris iš „getLCA“ () funkcijai perduodamų mazgų atitinka šaknį, tada šaknis bus LCA, ir nereikia atlikti jokio atkūrimo.

Bandymo atvejai [1] Ir n1, ir n2 yra medyje ir yra abiejose jų pagrindinio mazgo pusėse. [2] Bet kuris mazgas n1 arba n2 yra šaknis, LCA yra šaknis. [3] Medyje, tik n1 arba n2, LCA bus arba medžio šaknies kairiojo subteto mazgo šaknis, arba LCA bus medžio šaknies dešiniojo šaknies šaknis.

[4] N1 ir n2 nėra medyje, nėra LCA. [5] Tiek n1, tiek n2 yra tiesia linija viena šalia kitos, LCA bus arba iš n1, arba n2, kuris kada nors uždaro medžio šaknį.

 //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
10 янв. atsakymas, kurį pateikė gilla07 10 sausis 2015-01-10 18:35 '15, 18:35, 2015-01-10 18:35

Tiesiog eikite nuo viso root medžio, o abu nurodyti mazgai, pvz., „ p ir „ q , kuriems reikia rasti protėvį, yra toje pačioje subtree (tai reiškia, kad jų vertės yra mažesnės arba abu yra didesnės už šaknų vertes).

Tai vyksta tiesiai nuo šaknų iki mažiausiai paplitusio protėvio, nepaisant likusios medžio dalies, todėl ji vystosi gana greitai. Keletas būdų tai padaryti.

Iteratyvi, O (1) erdvė

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

perpildymo atveju, norėčiau padaryti (root.val - (ilgas) p.val) * (root.val - (ilgas) q.val)

Rekursyvus

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
26 дек. Atsakymas duotas Rajnish 26 dec. 2015-12-26 21:07 '15 - 21:07 2015-12-26 21:07

Scala kodu:

 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
01 дек. Jatino atsakymas: gruodžio 1 d 2012-12-01 20:28 '12 at 8:28 pm 2012-12-01 20:28

Jei tai yra pilnas dvejetainis medis su mazgo x vaikais kaip 2 * x ir 2 * x + 1, tai yra greitesnis būdas tai padaryti

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

Kaip tai veikia

  • gauti bitą, reikalingą x ir y, kurie, naudojant dvejetainę paiešką, yra O (log (32))
  • bendrasis dvejetainis prefiksas x ir y yra bendras protėvis
  • priklausomai nuo to, ką vaizduoja didelis bitų skaičius, k → diff
  • k = x ^ y ištrina bendrą prefiksą x ir y
  • suraskite bitų, atstovaujančių likusį priesagą
  • perkelkite x arba y per priesagos bitus, kad gautumėte bendrą prefiksą, kuris yra bendras protėvis.

Tai veikia, nes iš esmės dalijant didesnį skaičių į du rekursiškus, kol abu numeriai yra lygūs. Šis skaičius yra bendras protėvis. Išskyrimas iš tiesų yra teisingas poslinkis. Todėl, norėdami rasti artimiausią protėvį, turime rasti bendrą dviejų skaičių prefiksą

1
11 апр. atsakymas, kurį davė įsilaužėlių hakeris 11 balandžio. 2014-04-11 12:56 '14 at 12:56 2014-04-11 12:56
 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 subtrees } 
1
10 марта '13 в 12:51 2013-03-10 12:51 atsakymas pateikiamas Krishnachandra Sharma, kovo 13 d., 13 val. 12:51 2013-03-10 12:51

Galbūt kitas požiūris. Tačiau tai nėra tokia veiksminga, kaip jau pasiūlyta atsakymuose.

  • Sukurkite mazgo n1 kelio vektorių.

  • Sukurkite antrą kelio vektorių mazge n2.

  • Kelio vektorius reiškia, kad tam tikri mazgai nuo to judės, kad pasiektų atitinkamą mazgą.

  • Palyginkite abu kelio vektorius. Indeksas, kuriame jie nesutampa, grąžina mazgo į šį indeksą - 1. Tai suteiks LCA.

Trūkumai dėl šio požiūrio:

Du kartus reikia pereiti per medį, kad apskaičiuotumėte kelio vektorius. Papildoma O (h) erdvė reikalinga kelio vektorių saugojimui.

Tačiau tai lengva įdiegti ir suprasti.

Kelio vektoriaus skaičiavimo kodas:

 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
28 июля '15 в 14:31 2015-07-28 14:31 atsakymą pateikė Sumit Trehan liepos 28 d., 15 val. 14:31 2015-07-28 14:31
 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
15 февр. atsakymas, kurį pateikė „ HeadAndTail“ vasario 15 d 2018-02-15 16:03 '18, 4:03 pm 2018-02-15 16:03

Kai kurie čia pateikti sprendimai leidžia manyti, kad yra ryšys su mazgo šaknimi, kai kurie mano, kad medis yra BST. Dalijimasis mano sprendimu naudojant „hashmap“ be nuorodos į root mazgų ir medis gali būti BST arba ne 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 } 
0
28 июня '17 в 4:17 2017-06-28 04:17 atsakymą pateikė Janusbalatbat birželio 28 d. 17 d. 4:17 2017-06-28 04:17

Jūs teisus, kad be pagrindinio mazgo, problemos sprendimo būdas suteiks jums O (n) laiko sudėtingumą.

Sprendimo metodas Tarkime, kad LCA yra mazgas A ir B, paprasčiausias būdas yra iš pradžių gauti kelią nuo šaknies iki A, o tada gauti kelią nuo šaknies iki B. Po to, kai einate per šiuos du kelius, galite lengvai pasikartoti per juos ir suraskite paskutinį bendrąjį mazgą, kuris yra mažiausias bendrasis A ir B protėvis.

Rekursinis sprendimas Kitas būdas yra panaudoti rekursiją. Pirma, mes galime gauti LCA iš kairiojo medžio ir dešiniojo medžio (jei jis yra). Jei vienas iš A arba B yra mazgo šaknis, tada šaknis yra LCA, ir mes tiesiog grąžinsime šaknį, kuri yra rekursijos galutinis taškas. Kadangi ir toliau medį padalijame į subtrees, galiausiai mes streikuojame gerai su A arba B.

Suderinti sprendimus sprendžiant problemas, jei LCA (kairysis medis) grąžina mazgą, žinome, kad A ir B yra kairiajame medyje, o grįžtas mazgas yra galutinis rezultatas. Jei tiek LCA (kairėje), tiek LCA (dešinėje) grąžina nebaigtus mazgus, tai reiškia, kad A ir B yra atitinkamai kairiajame ir dešiniame medyje. Tokiu atveju mazgo šaknis yra mažiausias bendras mazgas.

Patikrinkite išsamią analizę ir sprendimą Mažiausias bendras protėvis .

0
07 июля '16 в 18:34 2016-07-07 18:34 atsakymas pateiktas Mark 07 liepos 16 d. 18:34 2016-07-07 18:34

Pirmosios paieškos lauko kodas, užtikrinantis, kad abu mazgai būtų medyje. Tik tada pereikite prie LCA paieškos. Komentuokite, jei turite kokių nors pasiūlymų dėl patobulinimų. Manau, kad mes galbūt galime juos pažymėti lankytojais ir iš naujo paleisti paiešką tam tikru momentu, kai sustojome, kad pagerintume antrąjį mazgą (jei jo nerasta 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; } } 
0
06 апр. Neelesh Salian atsakymas 2016-04-06 06:51 '16 at 6:51 2016-04-06 06:51

Neapdorotas būdas:

  • Kiekviename mazge
    • X = rasti, jei bet kuris iš n1, n2 egzistuoja kairėje mazgo pusėje
    • Y = rasti, jei bet kuris iš n1, n2 egzistuoja dešinėje mazgo pusėje
      • jei mazgas yra n1 || n2, galime jį vadinti kairėje arba dešinėje, kad būtų apibendrinti.
    • Jei X ir Y yra teisingi, tada mazgas yra CA

Problema, susijusi su aukščiau pateiktu metodu, yra ta, kad „surasime“ kelis kartus, t.y. yra galimybė, kad kiekvienas mazgas praeis kelis kartus. Mes galime įveikti šią problemą, jei galime rašyti informaciją, kad jos nebebūtume apdorojamos (pagalvokite apie dinaminį programavimą).

Todėl, užuot suradę kiekvieną mazgą, mes registruojame, kas jau buvo rastas.

Geriausias būdas:

  • Mes patikriname, ar tam tikras mazgas yra kairioji (tai reiškia, kad n1 | n2 buvo rasta kairėje subtree) arba right_set su pirmuoju gyliu. (PASTABA: mes suteikiame šaknies kairiojo_seto turtą, jei jis yra arba n1 | n2)
  • Jei ir kairysis, ir dešinysis, tada mazgas yra LCA.

kodas:

 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,  if (leftCA) { return leftCA; } } if (!right_set) { rightCA= findCA(root->right, n1, n2,  if(rightCA) { return rightCA; } } if (left_set  right_set) { return root; } else { *set = (left_set || right_set); return NULL; } } 
0
09 окт. Shatru Sadhu atsakymas 09 Oct 2015-10-09 17:54 '15, 17:54, 2015-10-09 17:54

Išbandykite

 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
20 сент. atsakymas pateikiamas Shubhamv rugsėjo 20 d 2015-09-20 12:09 '15 , 12:09 2015-09-20 12:09

Nors tai jau buvo atsakyta, tai yra mano požiūris į šią problemą naudojant C programavimo kalbą, nors kode rodomas dvejetainis paieškos medis (atsižvelgiant į įterpimą ()), tačiau algoritmas veikia ir dvejetainiam medžiui. Idėja yra pasikartoti per visus mazgus, esančius nuo A mazgo iki mazgo B, ir ieškokite jų indeksų. Mažiausias bendras protėvis yra mazgas, kurio didžiausias indeksas yra žiedo sankryžoje.

Tai darbinis C kodas, skirtas funkcijai įgyvendinti, norint ieškoti mažiausio bendrojo protėvio dvejetainiame medyje. Aš taip pat teikiu visas naudingumo funkcijas ir tt Tačiau eikite į CommonAncestor (), kad galėtumėte greitai suprasti.

 #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; }  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); }  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;  //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);  inorder(root, IN_ORDER);  postorder(root, POST_ORDER); CommonAncestor(1, 100); } 
0
ответ дан Gaurav Sinha 15 янв. '15 в 11:25 2015-01-15 11:25