AVANTPASSAT COMÚ MÉS BAIX EN UN ARBRE BINARI - TECHCODEVIEW.COM

Què és l'avantpassat comú més baix de l'arbre binari?

El ancestre comú més baix és el node més baix de l'arbre que té n1 i n2 com descendents, on n1 i n2 són els nodes per als quals volem trobar l'LCA. Per tant, l'LCA d'un arbre binari amb nodes n1 i n2 és l'ancestre compartit de n1 i n2 que es troba més lluny de l'arrel.

Aplicació de l'ancestre comú més baix (LCA):

Per determinar la distància entre parells de nodes d'un arbre: la distància de n1 a n2 es pot calcular com la distància de l'arrel a n1, més la distància de l'arrel a n2, menys el doble de la distància de l'arrel al seu comú més baix. avantpassat.

Avantpassat comú més baix a l'arbre binari

Pràctica recomanada L'avantpassat comú més baix en un arbre binari Prova-ho!

Avantpassat comú més baix en un arbre binari emmagatzemant camins des de l'arrel a n1 i de l'arrel a n2:

La idea d'aquest enfocament és emmagatzemar el camí de l'arrel a n1 i arrel a n2 en dues estructures de dades separades. A continuació, busqueu simultàniament els valors emmagatzemats a l'estructura de dades i cerqueu el primer desajust.

Il·lustració:

Trobeu l'LCA de 5 i 6

Camí de l'arrel a 5 = { 1, 2, 5 }
Camí de l'arrel a 6 = { 1, 3, 6 }

Comencem a comprovar des de l'índex 0. Com que tots dos valors coincideixen (pathA[0] = pathB[0] ), passem al següent índex.

pathA[1] no és igual a pathB[1], hi ha un desajustament així que considerem el valor anterior.

Per tant, l'LCA de (5,6) = 1

Seguiu els passos següents per resoldre el problema:

Trobeu un camí des de l'arrel fins a n1 i emmagatzemeu-lo en un vector o matriu.
Trobeu un camí des de l'arrel fins a n2 i deseu-lo en un altre vector o matriu.
Travessa ambdós camins fins que els valors de les matrius siguin els mateixos. Retorna l'element comú just abans del desajust.

A continuació es mostra la implementació de l'algorisme anterior:

C++

// C++ Program for Lowest Common Ancestor> // in a Binary Tree> // A O(n) solution to find LCA> // of two given values n1 and n2> #include> using> namespace> std;> // A Binary Tree node> struct> Node {> >int> key;> >struct> Node *left, *right;> };> // Utility function creates a new binary tree node with> // given key> Node* newNode(>int> k)> {> >Node* temp =>new> Node;> >temp->clau = k;> >temp->esquerra = temp->dreta = NULL;> >return> temp;> }> // Finds the path from root node to given root of the tree,> // Stores the path in a vector path[], returns true if path> // exists otherwise false> bool> findPath(Node* root, vector<>int>>& camí,>>>k)> (root->dreta && findPath(arrel->dreta, camí, k)))> >return> true>;> >// If not present in subtree rooted with root, remove> >// root from path[] and return false> >path.pop_back();> >return> false>;> > // Returns LCA if node n1, n2 are present in the given> // binary tree, otherwise return -1> int> findLCA(Node* root,>int> n1,>int> n2)> > // Driver program to test above functions> int> main()> {> >// Let us create the Binary Tree shown in above diagram.> >Node* root = newNode(1);> >root->esquerre = nouNode(2);> >root->dreta = nouNode(3);> >root->esquerra->esquerra = nouNode(4);> >root->esquerra->dreta = nouNode(5);> >root->dreta->esquerra = nouNode(6);> >root->dreta->dreta = nouNode(7);> >cout <<>'LCA(4, 5) = '> << findLCA(root, 4, 5);> >cout <<>

'
LCA(4, 6) = '>

<< findLCA(root, 4, 6);> >cout <<>

'
LCA(3, 4) = '>

<< findLCA(root, 3, 4);> >cout <<>

'
LCA(2, 4) = '>

<< findLCA(root, 2, 4);> >return> 0;> }>

Java

// Java Program for Lowest Common Ancestor> // in a Binary Tree> // A O(n) solution to find LCA of> // two given values n1 and n2> import> java.util.ArrayList;> import> java.util.List;> // A Binary Tree node> class> Node {> >int> data;> >Node left, right;> >Node(>int> value)> >{> >data = value;> >left = right =>null>;> >}> }> public> class> BT_NoParentPtr_Solution1 {> >Node root;> >private> List path1 =>new> ArrayList();> >private> List path2 =>new> ArrayList();> >// Finds the path from root node to given root of the> >// tree.> >int> findLCA(>int> n1,>int> n2)> >{> >path1.clear();> >path2.clear();> >return> findLCAInternal(root, n1, n2);> >}> >private> int> findLCAInternal(Node root,>int> n1,>int> n2)> >{> >if> (!findPath(root, n1, path1)> >|| !findPath(root, n2, path2)) {> >System.out.println((path1.size()>>0>)> >?>'n1 is present'> >:>'n1 is missing'>);> >System.out.println((path2.size()>>0>)> >?>'n2 is present'> >:>'n2 is missing'>);> >return> ->1>;> >}> >int> i;> >for> (i =>0>

; i   i++) {  // System.out.println(path1.get(i) + ' ' +  // path2.get(i));  if (!path1.get(i).equals(path2.get(i)))  break;  }  return path1.get(i - 1);  }  // Finds the path from root node to given root of the  // tree, Stores the path in a vector path[], returns  // true if path exists otherwise false  private boolean findPath(Node root, int n,  List path)  {  // base case  if (root == null) {  return false;  }  // Store this node . The node will be removed if  // not in path from root to n.  path.add(root.data);  if (root.data == n ||  findPath(root.left, n, path) ||  findPath(root.right, n, path)) {  return true;  }  // If not present in subtree rooted with root,  // remove root from path[] and return false  path.remove(path.size() - 1);  return false;  }  // Driver code  public static void main(String[] args)  {  BT_NoParentPtr_Solution1 tree  = new BT_NoParentPtr_Solution1();  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.left = new Node(6);  tree.root.right.right = new Node(7);  System.out.println('LCA(4, 5) = '  + tree.findLCA(4, 5));  System.out.println('LCA(4, 6) = '  + tree.findLCA(4, 6));  System.out.println('LCA(3, 4) = '  + tree.findLCA(3, 4));  System.out.println('LCA(2, 4) = '  + tree.findLCA(2, 4));  } } // This code is contributed by Sreenivasulu Rayanki.>

Python 3

# Python Program for Lowest Common Ancestor in a Binary Tree> # O(n) solution to find LCS of two given values n1 and n2> # A binary tree node> class> Node:> ># Constructor to create a new binary node> >def> __init__(>self>, key):> >self>.key>=> key> >self>.left>=> None> >self>.right>=> None> # Finds the path from root node to given root of the tree.> # Stores the path in a list path[], returns true if path> # exists otherwise false> def> findPath(root, path, k):> ># Baes Case> >if> root>is> None>:> >return> False> ># Store this node is path vector. The node will be> ># removed if not in path from root to k> >path.append(root.key)> ># See if the k is same as root's key> >if> root.key>=>=> k:> >return> True> ># Check if k is found in left or right sub-tree> >if> ((root.left !>=> None> and> findPath(root.left, path, k))>or> >(root.right !>=> None> and> findPath(root.right, path, k))):> >return> True> ># If not present in subtree rooted with root, remove> ># root from path and return False> >path.pop()> >return> False> # Returns LCA if node n1 , n2 are present in the given> # binary tree otherwise return -1> def> findLCA(root, n1, n2):> ># To store paths to n1 and n2 fromthe root> >path1>=> []> >path2>=> []> ># Find paths from root to n1 and root to n2.> ># If either n1 or n2 is not present , return -1> >if> (>not> findPath(root, path1, n1)>or> not> findPath(root, path2, n2)):> >return> ->1> ># Compare the paths to get the first different value> >i>=> 0> >while>(i <>len>(path1)>and> i <>len>(path2)):> >if> path1[i] !>=> path2[i]:> >break> >i>+>=> 1> >return> path1[i>->1>]> # Driver program to test above function> if> __name__>=>=> '__main__'>:> > ># Let's create the Binary Tree shown in above diagram> >root>=> Node(>1>)> >root.left>=> Node(>2>)> >root.right>=> Node(>3>)> >root.left.left>=> Node(>4>)> >root.left.right>=> Node(>5>)> >root.right.left>=> Node(>6>)> >root.right.right>=> Node(>7>)> > >print>(>'LCA(4, 5) = %d'> %> (findLCA(root,>4>,>5>,)))> >print>(>'LCA(4, 6) = %d'> %> (findLCA(root,>4>,>6>)))> >print>(>'LCA(3, 4) = %d'> %> (findLCA(root,>3>,>4>)))> >print>(>'LCA(2, 4) = %d'> %> (findLCA(root,>2>,>4>)))> # This code is contributed by Nikhil Kumar Singh(nickzuck_007)>

C#

// C# Program for Lowest Common> // Ancestor in a Binary Tree> // A O(n) solution to find LCA> // of two given values n1 and n2> using> System.Collections;> using> System;> // A Binary Tree node> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> value)> >{> >data = value;> >left = right =>null>;> >}> }> public> class> BT_NoParentPtr_Solution1 {> >Node root;> >private> ArrayList path1 =>new> ArrayList();> >private> ArrayList path2 =>new> ArrayList();> >// Finds the path from root> >// node to given root of the> >// tree.> >int> findLCA(>int> n1,>int> n2)> >{> >path1.Clear();> >path2.Clear();> >return> findLCAInternal(root, n1, n2);> >}> >private> int> findLCAInternal(Node root,>int> n1,>int> n2)> >{> >if> (!findPath(root, n1, path1)> >|| !findPath(root, n2, path2)) {> >Console.Write((path1.Count>0)> >?>'n1 is present'> >:>'n1 is missing'>);> >Console.Write((path2.Count>0)> >?>'n2 is present'> >:>'n2 is missing'>);> >return> -1;> >}> >int> i;> >for>

(i = 0; i   i++) {  // System.out.println(path1.get(i)  // + ' ' + path2.get(i));  if ((int)path1[i] != (int)path2[i])  break;  }  return (int)path1[i - 1];  }  // Finds the path from root node  // to given root of the tree,  // Stores the path in a vector  // path[], returns true if path  // exists otherwise false  private bool findPath(Node root, int n, ArrayList path)  {  // base case  if (root == null) {  return false;  }  // Store this node . The node  // will be removed if not in  // path from root to n.  path.Add(root.data);  if (root.data == n) {  return true;  }  if (root.left != null  && findPath(root.left, n, path)) {  return true;  }  if (root.right != null  && findPath(root.right, n, path)) {  return true;  }  // If not present in subtree  // rooted with root, remove root  // from path[] and return false  path.RemoveAt(path.Count - 1);  return false;  }  // Driver code  public static void Main(String[] args)  {  BT_NoParentPtr_Solution1 tree  = new BT_NoParentPtr_Solution1();  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.left = new Node(6);  tree.root.right.right = new Node(7);  Console.Write('LCA(4, 5) = ' + tree.findLCA(4, 5));  Console.Write('
LCA(4, 6) = '  + tree.findLCA(4, 6));  Console.Write('
LCA(3, 4) = '  + tree.findLCA(3, 4));  Console.Write('
LCA(2, 4) = '  + tree.findLCA(2, 4));  } } // This code is contributed by Rutvik_56>

Javascript

> >// JavaScript Program for Lowest Common> >// Ancestor in a Binary Tree> >// A O(n) solution to find LCA of> >// two given values n1 and n2> > >class Node> >{> >constructor(value) {> >this>.left =>null>;> >this>.right =>null>;> >this>.data = value;> >}> >}> > >let root;> >let path1 = [];> >let path2 = [];> > >// Finds the path from root node to given root of the tree.> >function> findLCA(n1, n2) {> >path1 = [];> >path2 = [];> >return> findLCAInternal(root, n1, n2);> >}> > >function> findLCAInternal(root, n1, n2) {> > >if> (!findPath(root, n1, path1) || !findPath(root, n2, path2))> >{> >document.write((path1.length>0) ?> >'n1 is present'> :>'n1 is missing'>);> >document.write((path2.length>0) ?> >'n2 is present'> :>'n2 is missing'>);> >return> -1;> >}> > >let i;> >for>

(i = 0; i     // System.out.println(path1.get(i) + ' ' + path2.get(i));  if (path1[i] != path2[i])  break;  }    return path1[i-1];  }    // Finds the path from root node to   // given root of the tree, Stores the  // path in a vector path[], returns true  // if path exists otherwise false  function findPath(root, n, path)  {  // base case  if (root == null) {  return false;  }    // Store this node . The node will be removed if  // not in path from root to n.  path.push(root.data);    if (root.data == n) {  return true;  }    if (root.left != null && findPath(root.left, n, path)) {  return true;  }    if (root.right != null && findPath(root.right, n, path)) {  return true;  }    // If not present in subtree rooted with root,   // remove root from  // path[] and return false  path.pop();    return false;  }    root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.left = new Node(6);  root.right.right = new Node(7);  document.write('LCA(4, 5) = ' + findLCA(4,5) + '');  document.write('LCA(4, 6) = ' + findLCA(4,6) + '');  document.write('LCA(3, 4) = ' + findLCA(3,4) + '');  document.write('LCA(2, 4) = ' + findLCA(2,4));>

Sortida

LCA(4, 5) = 2 LCA(4, 6) = 1 LCA(3, 4) = 1 LCA(2, 4) = 2>

Complexitat temporal: O(N). L'arbre es recorre dues vegades i després es comparen les matrius de camins.
Espai auxiliar: O(N). Espai addicional per al camí 1 i el camí 2.

Avantpassat comú més baix en un arbre binari per travessia única:

La idea és recórrer l'arbre partint de l'arrel. Si alguna de les claus donades (n1 i n2) coincideix amb l'arrel, llavors l'arrel és LCA (suposant que les dues claus estan presents). Si l'arrel no coincideix amb cap de les claus, repetirem el subarbre esquerre i dret.

El node que té una clau present al seu subarbre esquerre i l'altra clau present al subarbre dret és l'LCA.

Si les dues claus es troben al subarbre esquerre, llavors el subarbre esquerre també té LCA,

En cas contrari, LCA es troba al subarbre correcte.

Il·lustració:

Trobeu l'LCA de 5 i 6

Arrel està apuntant al node amb el valor 1, ja que el seu valor no coincideix amb { 5, 6 }. Busquem la clau al subarbre esquerre i al subarbre dret.

Subarbre esquerre:

Nova arrel = { 2 } ≠ 5 o 6, per tant continuarem la nostra recursivitat

Nova arrel = {4}, el subarbre esquerre i dret és nul, retornarem NULL per a aquesta trucada

New Root = { 5 } , el valor coincideix amb 5, de manera que retornarà el node amb el valor 5

La crida de funció per a root amb el valor 2 retornarà un valor de 5

Subarbre dret:

Arrel = { 3 } ≠ 5 o 6, per tant continuem la nostra recursivitat

Arrel = { 6 } = 5 o 6 , retornarem aquest node amb el valor 6

Arrel = { 7 } ≠ 5 o 6, retornarem NULL

Per tant, la crida de funció per a root amb el valor 3 retornarà el node amb el valor 6

Com que tant el subarbre esquerre com el subarbre dret del node amb el valor 1 no són NULL, per tant 1 és l'LCA

Seguiu els passos següents per resoldre el problema:

Passem l'arrel a una funció auxiliar i comprovem si el valor de l'arrel coincideix amb n1 i n2.
- En cas afirmatiu, retorneu l'arrel
- sinó crida recursiva al subarbre esquerre i dret
Bàsicament, fem un recorregut de pre-ordre, al principi comprovem si l'arrel->valor coincideix amb n1 o n2. A continuació, travessa pel subarbre esquerre i dret.
Si hi ha alguna arrel que retorni un valor NULL i un altre valor NON-NULL, retornarem el valor NON-NULL corresponent per a aquest node.
El node que retorna els dos valors NO NULL per al subarbre esquerre i dret, és el nostre avantpassat comú més baix.

A continuació es mostra la implementació de l'enfocament anterior.

C++

/* C++ Program to find LCA of n1 and n2 using one traversal> >* of Binary Tree */> #include> using> namespace> std;> // A Binary Tree Node> struct> Node {> >struct> Node *left, *right;> >int> key;> };> // Utility function to create a new tree Node> Node* newNode(>int> key)> {> >Node* temp =>new> Node;> >temp->clau = clau;> >temp->esquerra = temp->dreta = NULL;> >return> temp;> }> // This function returns pointer to LCA of two given values> // n1 and n2. This function assumes that n1 and n2 are> // present in Binary Tree> struct> Node* findLCA(>struct> Node* root,>int> n1,>int> n2)> > >// Base case> >if> (root == NULL)> >return> NULL;> >// If either n1 or n2 matches with root's key, report> >// the presence by returning root (Note that if a key is> >// ancestor of other, then the ancestor key becomes LCA> >if> (root->clau == n1>>> int> main()> {> >// Let us create binary tree given in the above example> >Node* root = newNode(1);> >root->esquerra = nouNode(2);> >root->dreta = nouNode(3);> >root->esquerra->esquerra = nouNode(4);> >root->esquerra->dreta = nouNode(5);> >root->dreta->esquerra = nouNode(6);> >root->dreta->dreta = nouNode(7);> >cout <<>'LCA(4, 5) = '>

  cout << '
LCA(4, 6) = '   cout << '
LCA(3, 4) = '   cout << '
LCA(2, 4) = '   return 0; } // This code is contributed by Aditya Kumar (adityakumar129)>

C

// C Program to find LCA of n1 and n2 using one traversalof> // Binary Tree> #include> #include> // A Binary Tree Node> typedef> struct> Node {> >struct> Node *left, *right;> >int> key;> } Node;> // Utility function to create a new tree Node> Node* newNode(>int> key)> {> >Node* temp = (Node*)>malloc>(>sizeof>(Node));> >temp->clau = clau;> >temp->esquerra = temp->dreta = NULL;> >return> temp;> }> // This function returns pointer to LCA of two given values> // n1 and n2. This function assumes that n1 and n2 are> // present in Binary Tree> Node* findLCA(Node* root,>int> n1,>int> n2)> > >// Base case> >if> (root == NULL)> >return> NULL;> >// If either n1 or n2 matches with root's key, report> >// the presence by returning root (Note that if a key is> >// ancestor of other, then the ancestor key becomes LCA> >if> (root->clau == n1>>> int> main()> {> >// Let us create binary tree given in the above example> >Node* root = newNode(1);> >root->esquerre = nouNode(2);> >root->dreta = nouNode(3);> >root->esquerra->esquerra = nouNode(4);> >root->esquerra->dreta = nouNode(5);> >root->dreta->esquerra = nouNode(6);> >root->dreta->dreta = nouNode(7);> >printf>(>'LCA(4, 5) = %d'>, findLCA(root, 4, 5)->clau);> >printf>(>

'
LCA(4, 6) = %d'>

, findLCA(root, 4, 6)->clau);> >printf>(>

'
LCA(3, 4) = %d'>

, findLCA(root, 3, 4)->clau);> >printf>(>

'
LCA(2, 4) = %d'>

, findLCA(root, 2, 4)->clau);> >return> 0;> }> // This code is contributed by Aditya Kumar (adityakumar129)>

Java

// Java implementation to find lowest common ancestor of> // n1 and n2 using one traversal of binary tree> /* Class containing left and right child of current> >node and key value*/> class> Node {> >int> data;> >Node left, right;> >public> Node(>int> item)> >{> >data = item;> >left = right =>null>;> >}> }> public> class> BinaryTree {> >// Root of the Binary Tree> >Node root;> >Node findLCA(>int> n1,>int> n2)> >{> >return> findLCA(root, n1, n2);> >}> >// This function returns pointer to LCA of two given> >// values n1 and n2. This function assumes that n1 and> >// n2 are present in Binary Tree> >Node findLCA(Node node,>int> n1,>int> n2)> >> >// Base case> >if> (node ==>null>)> >return> null>;> >// If either n1 or n2 matches with root's key,> >// report the presence by returning root (Note that> >// if a key is ancestor of other, then the ancestor> >// key becomes LCA> >if> (node.data == n1> >/* Driver program to test above functions */> >public> static> void> main(String args[])> >{> >BinaryTree tree =>new> BinaryTree();> >tree.root =>new> Node(>1>);> >tree.root.left =>new> Node(>2>);> >tree.root.right =>new> Node(>3>);> >tree.root.left.left =>new> Node(>4>);> >tree.root.left.right =>new> Node(>5>);> >tree.root.right.left =>new> Node(>6>);> >tree.root.right.right =>new> Node(>7>);> >System.out.println(>'LCA(4, 5) = '> >+ tree.findLCA(>4>,>5>).data);> >System.out.println(>'LCA(4, 6) = '> >+ tree.findLCA(>4>,>6>).data);> >System.out.println(>'LCA(3, 4) = '> >+ tree.findLCA(>3>,>4>).data);> >System.out.println(>'LCA(2, 4) = '> >+ tree.findLCA(>2>,>4>).data);> >}> }>

Python 3

# Python program to find LCA of n1 and n2 using one> # traversal of Binary tree> # A binary tree node> class> Node:> ># Constructor to create a new tree node> >def> __init__(>self>, key):> >self>.key>=> key> >self>.left>=> None> >self>.right>=> None> # This function returns pointer to LCA of two given> # values n1 and n2> # This function assumes that n1 and n2 are present in> # Binary Tree> def> findLCA(root, n1, n2):> ># Base Case> >if> root>is> None>:> >return> None> ># If either n1 or n2 matches with root's key, report> ># the presence by returning root (Note that if a key is> ># ancestor of other, then the ancestor key becomes LCA> >if> root.key>=>=> n1>or> root.key>=>=> n2:> >return> root> ># Look for keys in left and right subtrees> >left_lca>=> findLCA(root.left, n1, n2)> >right_lca>=> findLCA(root.right, n1, n2)> ># If both of the above calls return Non-NULL, then one key> ># is present in once subtree and other is present in other,> ># So this node is the LCA> >if> left_lca>and> right_lca:> >return> root> ># Otherwise check if left subtree or right subtree is LCA> >return> left_lca>if> left_lca>is> not> None> else> right_lca> # Driver code> if> __name__>=>=> '__main__'>:> > ># Let us create a binary tree given in the above example> >root>=> Node(>1>)> >root.left>=> Node(>2>)> >root.right>=> Node(>3>)> >root.left.left>=> Node(>4>)> >root.left.right>=> Node(>5>)> >root.right.left>=> Node(>6>)> >root.right.right>=> Node(>7>)> >print>(>'LCA(4, 5) = '>, findLCA(root,>4>,>5>).key)> >print>(>'LCA(4, 6) = '>, findLCA(root,>4>,>6>).key)> >print>(>'LCA(3, 4) = '>, findLCA(root,>3>,>4>).key)> >print>(>'LCA(2, 4) = '>, findLCA(root,>2>,>4>).key)> # This code is contributed by Nikhil Kumar Singh(nickzuck_007)>

C#

// C# implementation to find lowest common> // ancestor of n1 and n2 using one traversal> // of binary tree> using> System;> // Class containing left and right> // child of current node and key value> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> item)> >{> >data = item;> >left = right =>null>;> >}> }> class> BinaryTree {> >// Root of the Binary Tree> >Node root;> >Node findLCA(>int> n1,>int> n2)> >{> >return> findLCA(root, n1, n2);> >}> >// This function returns pointer to LCA> >// of two given values n1 and n2. This> >// function assumes that n1 and n2 are> >// present in Binary Tree> >Node findLCA(Node node,>int> n1,>int> n2)> > node.data == n2)> >return> node;> >// Look for keys in left and right subtrees> >Node left_lca = findLCA(node.left, n1, n2);> >Node right_lca = findLCA(node.right, n1, n2);> >// If both of the above calls return Non-NULL,> >// then one key is present in once subtree> >// and other is present in other, So this> >// node is the LCA> >if> (left_lca !=>null> && right_lca !=>null>)> >return> node;> >// Otherwise check if left subtree or> >// right subtree is LCA> >return> (left_lca !=>null>) ? left_lca : right_lca;> >> >// Driver code> >public> static> void> Main(>string>[] args)> >{> >BinaryTree tree =>new> BinaryTree();> >tree.root =>new> Node(1);> >tree.root.left =>new> Node(2);> >tree.root.right =>new> Node(3);> >tree.root.left.left =>new> Node(4);> >tree.root.left.right =>new> Node(5);> >tree.root.right.left =>new> Node(6);> >tree.root.right.right =>new> Node(7);> >Console.WriteLine(>'LCA(4, 5) = '> >+ tree.findLCA(4, 5).data);> >Console.WriteLine(>'LCA(4, 6) = '> >+ tree.findLCA(4, 6).data);> >Console.WriteLine(>'LCA(3, 4) = '> >+ tree.findLCA(3, 4).data);> >Console.WriteLine(>'LCA(2, 4) = '> >+ tree.findLCA(2, 4).data);> >}> }> // This code is contributed by pratham76>

Javascript

> >// JavaScript implementation to find> >// lowest common ancestor of> >// n1 and n2 using one traversal of binary tree> > >class Node> >{> >constructor(item) {> >this>.left =>null>;> >this>.right =>null>;> >this>.data = item;> >}> >}> > >//Root of the Binary Tree> >let root;> > >function> findlCA(n1, n2)> >{> >return> findLCA(root, n1, n2);> >}> > >// This function returns pointer to LCA of two given> >// values n1 and n2. This function assumes that n1 and> >// n2 are present in Binary Tree> >function> findLCA(node, n1, n2)> >> > >root =>new> Node(1);> >root.left =>new> Node(2);> >root.right =>new> Node(3);> >root.left.left =>new> Node(4);> >root.left.right =>new> Node(5);> >root.right.left =>new> Node(6);> >root.right.right =>new> Node(7);> >document.write(>'LCA(4, 5) = '> +> >findlCA(4, 5).data +>''>);> >document.write(>'LCA(4, 6) = '> +> >findlCA(4, 6).data +>''>);> >document.write(>'LCA(3, 4) = '> +> >findlCA(3, 4).data +>''>);> >document.write(>'LCA(2, 4) = '> +> >findlCA(2, 4).data +>''>);> > >

Sortida

LCA(4, 5) = 2 LCA(4, 6) = 1 LCA(3, 4) = 1 LCA(2, 4) = 2>

Complexitat temporal : O(N) com el mètode fa un recorregut simple d'arbres de manera ascendente.
Espai auxiliar: O(H), on H és l'alçada de l'arbre.

Nota: El mètode anterior suposa això les claus estan presents a l'arbre binari . Si una clau està present i l'altra està absent, llavors retorna la clau actual com a LCA (l'ideal hauria d'haver retornat NULL). Podem estendre aquest mètode per gestionar tots els casos comprovant primer si n1 i n2 estan presents a l'arbre i després trobant l'LCA de n1 i n2. Per comprovar si el node està present a l'arbre binari o no, després travessa l'arbre per als dos nodes n1 i n2 per separat.

C++

/* C++ program to find LCA of n1 and n2 using one traversal> >of Binary Tree. It handles all cases even when n1 or n2> >is not there in Binary Tree */> #include> using> namespace> std;> // A Binary Tree Node> struct> Node {> >struct> Node *left, *right;> >int> key;> };> // Utility function to create a new tree Node> Node* newNode(>int> key)> {> >Node* temp =>new> Node;> >temp->clau = clau;> >temp->esquerra = temp->dreta = NULL;> >return> temp;> }> // This function returns pointer to LCA of two given> // valuesn1 and n2.> struct> Node* findLCAUtil(>struct> Node* root,>int> n1,>int> n2)> > // Returns true if key k is present in tree rooted with root> bool> find(Node* root,>int> k)> find(root->dret, k))> >return> true>;> >// Else return false> >return> false>;> > // This function returns LCA of n1 and n2 only if both n1> // and n2 are present in tree, otherwise returns NULL;> Node* findLCA(Node* root,>int> n1,>int> n2)> {> >// Return LCA only if both n1 and n2 are present in tree> >if> (find(root, n1) and find(root, n2))> >return> findLCAUtil(root, n1, n2);> >// Else return NULL> >return> NULL;> }> // Driver program to test above functions> int> main()> {> >// Let us create a binary tree given in the above> >// example> >Node* root = newNode(1);> >root->esquerra = nouNode(2);> >root->dreta = nouNode(3);> >root->esquerra->esquerra = nouNode(4);> >root->esquerra->dreta = nouNode(5);> >root->dreta->esquerra = nouNode(6);> >root->dreta->dreta = nouNode(7);> >Node* lca = findLCA(root, 4, 5);> >if> (lca != NULL)> >cout <<>'LCA(4, 5) = '>

  else  cout << 'Keys are not present ';  lca = findLCA(root, 4, 10);  if (lca != NULL)  cout << '
LCA(4, 10) = '   else  cout << '
Keys are not present ';  return 0; } // This code is contributed by Kshitij Dwivedi // (kshitijdwivedi28)>

Java

// Java implementation to find lowest common ancestor of> // n1 and n2 using one traversal of binary tree> // It also handles cases even when n1 and n2 are not there> // in Tree> /* Class containing left and right child of current node and> >* key */> class> Node {> >int> data;> >Node left, right;> >public> Node(>int> item)> >{> >data = item;> >left = right =>null>;> >}> }> public> class> BinaryTree {> >// Root of the Binary Tree> >Node root;> >static> boolean> v1 =>false>, v2 =>false>;> >// This function returns pointer to LCA of two given> >// values n1 and n2.> >// v1 is set as true by this function if n1 is found> >// v2 is set as true by this function if n2 is found> >Node findLCAUtil(Node node,>int> n1,>int> n2)> >{> >// Base case> >if> (node ==>null>)> >return> null>;> >// Store result in temp, in case of key match so> >// that we can search for other key also.> >Node temp =>null>;> >// If either n1 or n2 matches with root's key,> >// report the presence by setting v1 or v2 as true> >// and return root (Note that if a key is ancestor> >// of other, then the ancestor key becomes LCA)> >if> (node.data == n1) {> >v1 =>true>;> >temp = node;> >}> >if> (node.data == n2) {> >v2 =>true>;> >temp = node;> >}> >// Look for keys in left and right subtrees> >Node left_lca = findLCAUtil(node.left, n1, n2);> >Node right_lca = findLCAUtil(node.right, n1, n2);> >if> (temp !=>null>)> >return> temp;> >// If both of the above calls return Non-NULL, then> >// one key is present in once subtree and other is> >// present in other, So this node is the LCA> >if> (left_lca !=>null> && right_lca !=>null>)> >return> node;> >// Otherwise check if left subtree or right subtree> >// is LCA> >return> (left_lca !=>null>) ? left_lca : right_lca;> >}> >// Finds lca of n1 and n2 under the subtree rooted with> >// 'node'> >Node findLCA(>int> n1,>int> n2)> >{> >// Initialize n1 and n2 as not visited> >v1 =>false>;> >v2 =>false>;> >// Find lca of n1 and n2 using the technique> >// discussed above> >Node lca = findLCAUtil(root, n1, n2);> >// Return LCA only if both n1 and n2 are present in> >// tree> >if> (v1 && v2)> >return> lca;> >// Else return NULL> >return> null>;> >}> >/* Driver program to test above functions */> >public> static> void> main(String args[])> >{> >BinaryTree tree =>new> BinaryTree();> >tree.root =>new> Node(>1>);> >tree.root.left =>new> Node(>2>);> >tree.root.right =>new> Node(>3>);> >tree.root.left.left =>new> Node(>4>);> >tree.root.left.right =>new> Node(>5>);> >tree.root.right.left =>new> Node(>6>);> >tree.root.right.right =>new> Node(>7>);> >Node lca = tree.findLCA(>4>,>5>);> >if> (lca !=>null>)> >System.out.println(>'LCA(4, 5) = '> + lca.data);> >else> >System.out.println(>'Keys are not present'>);> >lca = tree.findLCA(>4>,>10>);> >if> (lca !=>null>)> >System.out.println(>'LCA(4, 10) = '> + lca.data);> >else> >System.out.println(>'Keys are not present'>);> >}> }>

Python 3

''' Program to find LCA of n1 and n2 using one traversal of> >Binary tree> It handles all cases even when n1 or n2 is not there in tree> '''> # A binary tree node> class> Node:> ># Constructor to create a new node> >def> __init__(>self>, key):> >self>.key>=> key> >self>.left>=> None> >self>.right>=> None> # This function return pointer to LCA of two given values> # n1 and n2> # v1 is set as true by this function if n1 is found> # v2 is set as true by this function if n2 is found> def> findLCAUtil(root, n1, n2, v):> ># Base Case> >if> root>is> None>:> >return> None> ># IF either n1 or n2 matches ith root's key, report> ># the presence by setting v1 or v2 as true and return> ># root (Note that if a key is ancestor of other, then> ># the ancestor key becomes LCA)> >if> root.key>=>=> n1:> >v[>0>]>=> True> >return> root> >if> root.key>=>=> n2:> >v[>1>]>=> True> >return> root> ># Look for keys in left and right subtree> >left_lca>=> findLCAUtil(root.left, n1, n2, v)> >right_lca>=> findLCAUtil(root.right, n1, n2, v)> ># If both of the above calls return Non-NULL, then one key> ># is present in once subtree and other is present in other,> ># So this node is the LCA> >if> left_lca>and> right_lca:> >return> root> ># Otherwise check if left subtree or right subtree is LCA> >return> left_lca>if> left_lca>is> not> None> else> right_lca> def> find(root, k):> ># Base Case> >if> root>is> None>:> >return> False> ># If key is present at root, or if left subtree or right> ># subtree , return true> >if> (root.key>=>=> k>or> find(root.left, k)>or> >find(root.right, k)):> >return> True> ># Else return false> >return> False> # This function returns LCA of n1 and n2 on value if both> # n1 and n2 are present in tree, otherwise returns None> def> findLCA(root, n1, n2):> ># Initialize n1 and n2 as not visited> >v>=> [>False>,>False>]> ># Find lca of n1 and n2 using the technique discussed above> >lca>=> findLCAUtil(root, n1, n2, v)> ># Returns LCA only if both n1 and n2 are present in tree> >if> (v[>0>]>and> v[>1>]>or> v[>0>]>and> find(lca, n2)>or> v[>1>]>and> >find(lca, n1)):> >return> lca> ># Else return None> >return> None> # Driver program to test above function> root>=> Node(>1>)> root.left>=> Node(>2>)> root.right>=> Node(>3>)> root.left.left>=> Node(>4>)> root.left.right>=> Node(>5>)> root.right.left>=> Node(>6>)> root.right.right>=> Node(>7>)> lca>=> findLCA(root,>4>,>5>)> if> lca>is> not> None>:> >print>(>'LCA(4, 5) = '>, lca.key)> else>:> >print>(>'Keys are not present'>)> lca>=> findLCA(root,>4>,>10>)> if> lca>is> not> None>:> >print>(>'LCA(4,10) = '>, lca.key)> else>:> >print>(>'Keys are not present'>)> # This code is contributed by Nikhil Kumar Singh(nickzuck_007)>

C#

using> System;> // c# implementation to find lowest common ancestor of> // n1 and n2 using one traversal of binary tree> // It also handles cases even when n1 and n2 are not there> // in Tree> /* Class containing left and right child of current node and> >* key */> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> item)> >{> >data = item;> >left = right =>null>;> >}> }> public> class> BinaryTree {> >// Root of the Binary Tree> >public> Node root;> >public> static> bool> v1 =>false>, v2 =>false>;> >// This function returns pointer to LCA of two given> >// values n1 and n2.> >// v1 is set as true by this function if n1 is found> >// v2 is set as true by this function if n2 is found> >public> virtual> Node findLCAUtil(Node node,>int> n1,> >int> n2)> >{> >// Base case> >if> (node ==>null>) {> >return> null>;> >}> >// Store result in temp, in case of key match so> >// that we can search for other key also.> >Node temp =>null>;> >// If either n1 or n2 matches with root's key,> >// report the presence by setting v1 or v2 as true> >// and return root (Note that if a key is ancestor> >// of other, then the ancestor key becomes LCA)> >if> (node.data == n1) {> >v1 =>true>;> >temp = node;> >}> >if> (node.data == n2) {> >v2 =>true>;> >temp = node;> >}> >// Look for keys in left and right subtrees> >Node left_lca = findLCAUtil(node.left, n1, n2);> >Node right_lca = findLCAUtil(node.right, n1, n2);> >if> (temp !=>null>) {> >return> temp;> >}> >// If both of the above calls return Non-NULL, then> >// one key is present in once subtree and other is> >// present in other, So this node is the LCA> >if> (left_lca !=>null> && right_lca !=>null>) {> >return> node;> >}> >// Otherwise check if left subtree or right subtree> >// is LCA> >return> (left_lca !=>null>) ? left_lca : right_lca;> >}> >// Finds lca of n1 and n2 under the subtree rooted with> >// 'node'> >public> virtual> Node findLCA(>int> n1,>int> n2)> >{> >// Initialize n1 and n2 as not visited> >v1 =>false>;> >v2 =>false>;> >// Find lca of n1 and n2 using the technique> >// discussed above> >Node lca = findLCAUtil(root, n1, n2);> >// Return LCA only if both n1 and n2 are present in> >// tree> >if> (v1 && v2) {> >return> lca;> >}> >// Else return NULL> >return> null>;> >}> >/* Driver program to test above functions */> >public> static> void> Main(>string>[] args)> >{> >BinaryTree tree =>new> BinaryTree();> >tree.root =>new> Node(1);> >tree.root.left =>new> Node(2);> >tree.root.right =>new> Node(3);> >tree.root.left.left =>new> Node(4);> >tree.root.left.right =>new> Node(5);> >tree.root.right.left =>new> Node(6);> >tree.root.right.right =>new> Node(7);> >Node lca = tree.findLCA(4, 5);> >if> (lca !=>null>) {> >Console.WriteLine(>'LCA(4, 5) = '> + lca.data);> >}> >else> {> >Console.WriteLine(>'Keys are not present'>);> >}> >lca = tree.findLCA(4, 10);> >if> (lca !=>null>) {> >Console.WriteLine(>'LCA(4, 10) = '> + lca.data);> >}> >else> {> >Console.WriteLine(>'Keys are not present'>);> >}> >}> }> // This code is contributed by Shrikant13>

Javascript

> // JavaScript implementation to find lowest> // common ancestor of n1 and n2 using one> // traversal of binary tree. It also handles> // cases even when n1 and n2 are not there in Tree> // Class containing left and right child> // of current node and key> class Node> {> >constructor(item)> >{> >this>.data = item;> >this>.left =>null>;> >this>.right =>null>;> >}> }> class BinaryTree{> > // Root of the Binary Tree> constructor()> {> >this>.root =>null>;> >this>.v1 =>false>;> >this>.v2 =>false>;> }> // This function returns pointer to LCA> // of two given values n1 and n2.> // v1 is set as true by this function> // if n1 is found> // v2 is set as true by this function> // if n2 is found> findLCAUtil(node, n1, n2)> {> > >// Base case> >if> (node ==>null>)> >{> >return> null>;> >}> > >// Store result in temp, in case of> >// key match so that we can search> >// for other key also.> >var> temp =>null>;> > >// If either n1 or n2 matches with root's key,> >// report the presence by setting v1 or v2 as> >// true and return root (Note that if a key> >// is ancestor of other, then the ancestor> >// key becomes LCA)> >if> (node.data == n1)> >{> >this>.v1 =>true>;> >temp = node;> >}> >if> (node.data == n2)> >{> >this>.v2 =>true>;> >temp = node;> >}> > >// Look for keys in left and right subtrees> >var> left_lca =>this>.findLCAUtil(node.left, n1, n2);> >var> right_lca =>this>.findLCAUtil(node.right, n1, n2);> > >if> (temp !=>null>)> >{> >return> temp;> >}> > >// If both of the above calls return Non-NULL,> >// then one key is present in once subtree and> >// other is present in other, So this node is the LCA> >if> (left_lca !=>null> && right_lca !=>null>)> >{> >return> node;> >}> > >// Otherwise check if left subtree or> >// right subtree is LCA> >return> left_lca !=>null> ? left_lca : right_lca;> }> // Finds lca of n1 and n2 under the> // subtree rooted with 'node'> findLCA(n1, n2)> {> > >// Initialize n1 and n2 as not visited> >this>.v1 =>false>;> >this>.v2 =>false>;> > >// Find lca of n1 and n2 using the> >// technique discussed above> >var> lca =>this>.findLCAUtil(>this>.root, n1, n2);> > >// Return LCA only if both n1 and n2> >// are present in tree> >if> (>this>.v1 &&>this>.v2)> >{> >return> lca;> >}> > >// Else return NULL> >return> null>;> }> }> // Driver code> var> tree =>new> BinaryTree();> tree.root =>new> Node(1);> tree.root.left =>new> Node(2);> tree.root.right =>new> Node(3);> tree.root.left.left =>new> Node(4);> tree.root.left.right =>new> Node(5);> tree.root.right.left =>new> Node(6);> tree.root.right.right =>new> Node(7);> var> lca = tree.findLCA(4, 5);> if> (lca !=>null>)> {> >document.write(>'LCA(4, 5) = '> +> >lca.data +>' '>);> }>else> {> >document.write(>'Keys are not present'> +>' '>);> }> lca = tree.findLCA(4, 10);> if> (lca !=>null>)> {> >document.write(>'LCA(4, 10) = '> +> >lca.data +>' '>);> }> else> {> >document.write(>'Keys are not present'> +>' '>);> }> // This code is contributed by rdtank> >

Sortida

LCA(4, 5) = 2 Keys are not present>

Complexitat temporal : O (N) com el mètode fa un recorregut simple d'arbres de manera ascendente.
Espai auxiliar: O(H), on h és l'alçada de l'arbre.

Ús d'una estructura de dades auxiliar (taula hash):

The basic idea behind the 'Using an auxiliary data structure' approach for finding the lowest common ancestor of two nodes in a binary tree is to use a hash table or a map to store the parent pointers of each node. Once we have the parent pointers, we can traverse up from the first node and add all its ancestors to a set or a list. Then we can traverse up from the second node and check if each ancestor is already in the set or the list. The first ancestor that is already in the set or the list is the lowest common ancestor.>

Seguiu els passos per implementar l'enfocament anterior:

Creeu una taula hash o un mapa per emmagatzemar els punters pare de cada node a l'arbre binari.
Travessa l'arbre binari i omple la taula hash o el mapa amb els punters pare per a cada node.
A partir del primer node, travessa l'arbre i afegeix cada avantpassat a un conjunt o una llista.
A partir del segon node, travessa l'arbre amunt i comprova si cada avantpassat ja és al conjunt o a la llista. El primer avantpassat que ja està al conjunt o a la llista és l'avantpassat comú més baix.
Si no es troba cap avantpassat comú, retorneu null o qualsevol altre valor que indiqui l'absència d'un avantpassat comú.

A continuació es mostra la implementació de l'enfocament anterior:

C++

// C++ code to implement above approach> #include> #include> #include> #include> using> namespace> std;> // Definition of a binary tree node> struct> Node {> >int> data;> >Node* left;> >Node* right;> };> // Function to create a new binary tree node> Node* newNode(>int> data)> {> >Node* node =>new> Node;> >node->dades = dades;> >node->esquerra = NULL;> >node->dreta = NULL;> >return> (node);> }> // Function to build a hash table or a map of parent> // pointers for each node in the tree> unordered_map buildParentMap(Node* root)> {> >unordered_map parentMap;> >parentMap[root] = NULL;> >vector queue = { root };> >while> (!queue.empty()) {> >Node* node = queue.front();> >queue.erase(queue.begin());> >if> (node->esquerra) {> >parentMap[node->esquerra] = node;> >queue.push_back(node->esquerra);> >}> >if> (node->dreta) {> >parentMap[node->dreta] = node;> >queue.push_back(node->dreta);> >}> >}> >return> parentMap;> }> // Function to find the lowest common ancestor of two nodes> // using an auxiliary data structure> int> findLCA(Node* root,>int> n1,>int> n2)> {> >// Build a hash table or a map of parent pointers for> >// each node in the tree> >unordered_map parentMap> >= buildParentMap(root);> >// Find the nodes with values n1 and n2> >Node* p = NULL;> >Node* q = NULL;> >vector queue = { root };> >while> (!queue.empty()) {> >Node* node = queue.front();> >queue.erase(queue.begin());> >if> (node->dades == n1) {> >p = node;> >}> >if> (node->dades == n2) {> >q = node;> >}> >if> (node->esquerra) {> >queue.push_back(node->esquerra);> >}> >if> (node->dreta) {> >queue.push_back(node->dreta);> >}> >}> >// Add all the ancestors of the first node to a set or a> >// list> >set ancestors;> >while> (p) {> >ancestors.insert(p);> >p = parentMap[p];> >}> >// Traverse up from the second node and check if each> >// ancestor is already in the set or the list> >while> (q) {> >if> (ancestors.find(q) != ancestors.end()) {> >return> q> >->dades;>>>>// already in the set or the list is> >// the lowest common ancestor> >}> >q = parentMap[q];> >}> >return> -1;>// No common ancestor found> }> // Driver code> int> main()> {> >Node* root = newNode(1);> >root->esquerra = nouNode(2);> >root->dreta = nouNode(3);> >root->esquerra->esquerra = nouNode(4);> >root->esquerra->dreta = nouNode(5);> >root->dreta->esquerra = nouNode(6);> >root->dreta->dreta = nouNode(7);> >cout <<>'LCA(4, 5) = '> << findLCA(root, 4, 5) << endl;> >cout <<>'LCA(4, 6) = '> << findLCA(root, 4, 6) << endl;> >cout <<>'LCA(3,4) = '> << findLCA(root, 3, 4) << endl;> >cout <<>'LCA(2, 4) = '> << findLCA(root, 2, 4) << endl;> >return> 0;> }> // This code is contributed by Veerendra_Singh_Rajpoot>

Java

import> java.util.*;> // Definition of a binary tree node> class> Node {> >int> data;> >Node left, right;> >public> Node(>int> item)> >{> >data = item;> >left = right =>null>;> >}> }> class> Main {> >// Function to build a hash table or a map of parent> >// pointers for each node in the tree> >static> Map buildParentMap(Node root)> >{> >Map parentMap =>new> HashMap();> >parentMap.put(root,>null>);> >Queue queue =>new> LinkedList();> >queue.add(root);> >while> (!queue.isEmpty()) {> >Node node = queue.poll();> >if> (node.left !=>null>) {> >parentMap.put(node.left, node);> >queue.add(node.left);> >}> >if> (node.right !=>null>) {> >parentMap.put(node.right, node);> >queue.add(node.right);> >}> >}> >return> parentMap;> >}> >// Function to find the lowest common ancestor of two> >// nodes using an auxiliary data structure> >static> int> findLCA(Node root,>int> n1,>int> n2)> >{> >// Build a hash table or a map of parent pointers> >// for each node in the tree> >Map parentMap = buildParentMap(root);> >// Find the nodes with values n1 and n2> >Node p =>null>, q =>null>;> >Queue queue =>new> LinkedList();> >queue.add(root);> >while> (!queue.isEmpty()) {> >Node node = queue.poll();> >if> (node.data == n1) {> >p = node;> >}> >if> (node.data == n2) {> >q = node;> >}> >if> (node.left !=>null>) {> >queue.add(node.left);> >}> >if> (node.right !=>null>) {> >queue.add(node.right);> >}> >}> >// Add all the ancestors of the first node to a set> >// or a list> >Set ancestors =>new> HashSet();> >while> (p !=>null>) {> >ancestors.add(p);> >p = parentMap.get(p);> >}> >// Traverse up from the second node and check if> >// each ancestor is already in the set or the list> >while> (q !=>null>) {> >if> (ancestors.contains(q)) {> >return> q.data;> >}> >q = parentMap.get(q);> >}> >return> ->1>;>// No common ancestor found> >}> >public> static> void> main(String[] args)> >{> >Node root =>new> Node(>1>);> >root.left =>new> Node(>2>);> >root.right =>new> Node(>3>);> >root.left.left =>new> Node(>4>);> >root.left.right =>new> Node(>5>);> >root.right.left =>new> Node(>6>);> >root.right.right =>new> Node(>7>);> >System.out.println(>'LCA(4, 5) = '> >+ findLCA(root,>4>,>5>));> >System.out.println(>'LCA(4, 6) = '> >+ findLCA(root,>4>,>6>));> >System.out.println(>'LCA(3, 4) = '> >+ findLCA(root,>3>,>4>));> >System.out.println(>'LCA(3, 4) = '> >+ findLCA(root,>2>,>4>));> >}> }>

Python 3

from> collections>import> deque> # Definition of a binary tree node> class> Node:> >def> __init__(>self>, data):> >self>.data>=> data> >self>.left>=> None> >self>.right>=> None> # Function to build a hash table or a map of parent> # pointers for each node in the tree> def> buildParentMap(root):> >parentMap>=> {}> >parentMap[root]>=> None> >queue>=> deque([root])> >while> queue:> >node>=> queue.popleft()> >if> node.left:> >parentMap[node.left]>=> node> >queue.append(node.left)> >if> node.right:> >parentMap[node.right]>=> node> >queue.append(node.right)> >return> parentMap> # Function to find the lowest common ancestor of two nodes> # using an auxiliary data structure> def> findLCA(root, n1, n2):> ># Build a hash table or a map of parent pointers for> ># each node in the tree> >parentMap>=> buildParentMap(root)> ># Find the nodes with values n1 and n2> >p, q>=> None>,>None> >queue>=> deque([root])> >while> queue:> >node>=> queue.popleft()> >if> node.data>=>=> n1:> >p>=> node> >if> node.data>=>=> n2:> >q>=> node> >if> node.left:> >queue.append(node.left)> >if> node.right:> >queue.append(node.right)> ># Add all the ancestors of the first node to a set or a> ># list> >ancestors>=> set>()> >while> p:> >ancestors.add(p)> >p>=> parentMap[p]> ># Traverse up from the second node and check if each> ># ancestor is already in the set or the list> >while> q:> >if> q>in> ancestors:> >return> q.data> >q>=> parentMap[q]> >return> ->1> # No common ancestor found> # Driver code> if> __name__>=>=> '__main__'>:> >root>=> Node(>1>)> >root.left>=> Node(>2>)> >root.right>=> Node(>3>)> >root.left.left>=> Node(>4>)> >root.left.right>=> Node(>5>)> >root.right.left>=> Node(>6>)> >root.right.right>=> Node(>7>)> >print>(>'LCA(4, 5) = '>, findLCA(root,>4>,>5>))> >print>(>'LCA(4, 6) = '>, findLCA(root,>4>,>6>))> >print>(>'LCA(3, 4) = '>, findLCA(root,>3>,>4>))> >print>(>'LCA(2, 4) = '>, findLCA(root,>2>,>4>))>

C#

using> System;> using> System.Collections.Generic;> // Definition of a binary tree node> class> Node> {> >public> int> data;> >public> Node left, right;> >public> Node(>int> item)> >{> >data = item;> >left = right =>null>;> >}> }> class> MainClass> {> >// Function to build a hash table or a map of parent> >// pointers for each node in the tree> >static> Dictionary BuildParentMap(Node root)> >{> >Dictionary parentMap =>new> Dictionary();> >parentMap.Add(root,>null>);> >Queue queue =>new> Queue();> >queue.Enqueue(root);> >while> (queue.Count != 0)> >{> >Node node = queue.Dequeue();> >if> (node.left !=>null>)> >{> >parentMap.Add(node.left, node);> >queue.Enqueue(node.left);> >}> >if> (node.right !=>null>)> >{> >parentMap.Add(node.right, node);> >queue.Enqueue(node.right);> >}> >}> >return> parentMap;> >}> >// Function to find the lowest common ancestor of two> >// nodes using an auxiliary data structure> >static> int> FindLCA(Node root,>int> n1,>int> n2)> >{> >// Build a hash table or a map of parent pointers> >// for each node in the tree> >Dictionary parentMap = BuildParentMap(root);> >// Find the nodes with values n1 and n2> >Node p =>null>, q =>null>;> >Queue queue =>new> Queue();> >queue.Enqueue(root);> >while> (queue.Count != 0)> >{> >Node node = queue.Dequeue();> >if> (node.data == n1)> >{> >p = node;> >}> >if> (node.data == n2)> >{> >q = node;> >}> >if> (node.left !=>null>)> >{> >queue.Enqueue(node.left);> >}> >if> (node.right !=>null>)> >{> >queue.Enqueue(node.right);> >}> >}> >// Add all the ancestors of the first node to a set> >// or a list> >HashSet ancestors =>new> HashSet();> >while> (p !=>null>)> >{> >ancestors.Add(p);> >p = parentMap[p];> >}> >// Traverse up from the second node and check if> >// each ancestor is already in the set or the list> >while> (q !=>null>)> >{> >if> (ancestors.Contains(q))> >{> >return> q.data;> >}> >q = parentMap[q];> >}> >return> -1;>// No common ancestor found> >}> >public> static> void> Main()> >{> >Node root =>new> Node(1);> >root.left =>new> Node(2);> >root.right =>new> Node(3);> >root.left.left =>new> Node(4);> >root.left.right =>new> Node(5);> >root.right.left =>new> Node(6);> >root.right.right =>new> Node(7);> >Console.WriteLine(>'LCA(4, 5) = '> + FindLCA(root, 4, 5));> >Console.WriteLine(>'LCA(4, 6) = '> + FindLCA(root, 4, 6));> >Console.WriteLine(>'LCA(3, 4) = '> + FindLCA(root, 3, 4));> >Console.WriteLine(>'LCA(2, 4) = '> + FindLCA(root, 2, 4));> >}> }> // This code is contributed by akashish__>

Javascript

// javascript code addition> // Definition of a binary tree node> class Node {> >constructor(item) {> >this>.data = item;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // Function to build a hash table or a map of parent> // pointers for each node in the tree> function> buildParentMap(root) {> >const parentMap =>new> Map();> >parentMap.set(root,>null>);> >const queue = [];> >queue.push(root);> >while> (queue.length>0) {> >const node = queue.shift();> >if> (node.left !=>null>) {> >parentMap.set(node.left, node);> >queue.push(node.left);> >}> >if> (node.right !=>null>) {> >parentMap.set(node.right, node);> >queue.push(node.right);> >}> >}> >return> parentMap;> }> // Function to find the lowest common ancestor of two> // nodes using an auxiliary data structure> function> findLCA(root, n1, n2) {> >// Build a hash table or a map of parent pointers> >// for each node in the tree> >const parentMap = buildParentMap(root);> >// Find the nodes with values n1 and n2> >let p =>null>, q =>null>;> >const queue = [];> >queue.push(root);> >while> (queue.length>0) {> >const node = queue.shift();> >if> (node.data === n1) {> >p = node;> >}> >if> (node.data === n2) {> >q = node;> >}> >if> (node.left !=>null>) {> >queue.push(node.left);> >}> >if> (node.right !=>null>) {> >queue.push(node.right);> >}> >}> >// Add all the ancestors of the first node to a set> >// or a list> >const ancestors =>new> Set();> >while> (p !=>null>) {> >ancestors.add(p);> >p = parentMap.get(p);> >}> >// Traverse up from the second node and check if> >// each ancestor is already in the set or the list> >while> (q !=>null>) {> >if> (ancestors.has(q)) {> >return> q.data;> >}> >q = parentMap.get(q);> >}> >return> -1;>// No common ancestor found> }> // Test the function> const root =>new> Node(1);> root.left =>new> Node(2);> root.right =>new> Node(3);> root.left.left =>new> Node(4);> root.left.right =>new> Node(5);> root.right.left =>new> Node(6);> root.right.right =>new> Node(7);> console.log(>'LCA(4, 5) = '> + findLCA(root, 4, 5));> console.log(>'LCA(4, 6) = '> + findLCA(root, 4, 6));> console.log(>'LCA(3, 4) = '> + findLCA(root, 3, 4));> console.log(>'LCA(2, 4) = '> + findLCA(root, 2, 4));> // The code is contributed by Nidhi goel.>

Sortida

LCA(4, 5) = 2 LCA(4, 6) = 1 LCA(3,4) = 1 LCA(2, 4) = 2>

Complexitat temporal: O(n),

món Wumpus

La complexitat temporal del codi donat és O(n), on n és el nombre de nodes de l'arbre binari.

La construcció del mapa pare per a cada node de l'arbre requereix visitar cada node una vegada, la qual cosa requereix temps O(n). Trobar els nodes amb valors n1 i n2 requereix visitar cada node una vegada, la qual cosa també requereix temps O(n). Desplaçar-se cap amunt des del segon node i comprovar si cada avantpassat ja està al conjunt o a la llista pren temps O(h), on h és l'alçada de l'arbre binari.

En el pitjor dels casos, l'alçada de l'arbre binari és O(n), si l'arbre binari està esbiaixat. Per tant, la complexitat temporal global del codi donat és O (n) + O (n) + O (n) = O (n).

Complexitat espacial: O(n),

La complexitat espacial del codi donat és O(n) en el pitjor dels casos. Això es deu al fet que la mida del mapa pare construït per a cada node de l'arbre és O(n). A més, el conjunt d'ancestres també pot contenir tots els nodes de l'arbre binari en el pitjor dels casos, que també ocupa espai O(n). Finalment, la cua utilitzada per recórrer l'arbre binari ocupa espai O(n). Per tant, la complexitat espacial global del codi donat és O(n) + O(n) + O(n) = O(n).

Hem parlat d'una solució eficient per trobar LCA a l'arbre de cerca binari. A l'arbre de cerca binari, utilitzant propietats BST, podem trobar LCA en el temps O(h) on h és l'alçada de l'arbre. Aquesta implementació no és possible a l'arbre binari, ja que els nodes de l'arbre binari de les claus no segueixen cap ordre.

També us pot agradar veure els articles següents:
LCA utilitzant Parent Pointer
Avantpassat comú més baix en un arbre de cerca binari.
Trobeu LCA a l'arbre binari mitjançant RMQ