Dado un árbol binario representado como una array principal, encuentre el ancestro común más bajo entre dos Nodes ‘m’ y ‘n’.
En el diagrama anterior, LCA de 10 y 14 es 12 y LCA de 10 y 12 es 12.
(1) Cree una array principal y almacene en ella el elemento principal del i-ésimo Node. El padre del Node raíz debe ser -1.
(2) Ahora, acceda a todos los Nodes desde el Node deseado ‘m’ hasta el Node raíz y márquelos como visitados.
(3) Por último, acceda a todos los Nodes desde el Node deseado ‘n’ hasta que llegue el primer Node visitado.
(4) Este Node es el ancestro común más bajo
C++
// CPP program to find LCA in a tree represented
// as parent array.
#include <bits/stdc++.h>
using namespace std;
// Maximum value in a node
const int MAX = 1000;
// Function to find the Lowest common ancestor
int findLCA(int n1, int n2, int parent[])
{
// Create a visited vector and mark
// all nodes as not visited.
vector<bool> visited(MAX, false);
visited[n1] = true;
// Moving from n1 node till root and
// mark every accessed node as visited
while (parent[n1] != -1) {
visited[n1] = true;
// Move to the parent of node n1
n1 = parent[n1];
}
visited[n1] = true;
// For second node finding the first
// node common
while (!visited[n2])
n2 = parent[n2];
return n2;
}
// Insert function for Binary tree
void insertAdj(int parent[], int i, int j)
{
parent[i] = j;
}
// Driver Function
int main()
{
// Maximum capacity of binary tree
int parent[MAX];
// Root marked
parent[20] = -1;
insertAdj(parent, 8, 20);
insertAdj(parent, 22, 20);
insertAdj(parent, 4, 8);
insertAdj(parent, 12, 8);
insertAdj(parent, 10, 12);
insertAdj(parent, 14, 12);
cout << findLCA(10, 14, parent);
return 0;
}
Java
// Java program to find LCA in a tree represented
// as parent array.
import java.util.*;
class GFG
{
// Maximum value in a node
static int MAX = 1000;
// Function to find the Lowest common ancestor
static int findLCA(int n1, int n2, int parent[])
{
// Create a visited vector and mark
// all nodes as not visited.
boolean []visited = new boolean[MAX];
visited[n1] = true;
// Moving from n1 node till root and
// mark every accessed node as visited
while (parent[n1] != -1)
{
visited[n1] = true;
// Move to the parent of node n1
n1 = parent[n1];
}
visited[n1] = true;
// For second node finding the first
// node common
while (!visited[n2])
n2 = parent[n2];
return n2;
}
// Insert function for Binary tree
static void insertAdj(int parent[], int i, int j)
{
parent[i] = j;
}
// Driver Function
public static void main(String[] args)
{
// Maximum capacity of binary tree
int []parent = new int[MAX];
// Root marked
parent[20] = -1;
insertAdj(parent, 8, 20);
insertAdj(parent, 22, 20);
insertAdj(parent, 4, 8);
insertAdj(parent, 12, 8);
insertAdj(parent, 10, 12);
insertAdj(parent, 14, 12);
System.out.println(findLCA(10, 14, parent));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program to find LCA in a # tree represented as parent array. # Maximum value in a node MAX = 1000 # Function to find the Lowest # common ancestor def findLCA(n1, n2, parent): # Create a visited vector and mark # all nodes as not visited. visited = [False for i in range(MAX)] visited[n1] = True # Moving from n1 node till root and # mark every accessed node as visited while (parent[n1] != -1): visited[n1] = True # Move to the parent of node n1 n1 = parent[n1] visited[n1] = True # For second node finding the # first node common while (visited[n2] == False): n2 = parent[n2] return n2 # Insert function for Binary tree def insertAdj(parent, i, j): parent[i] = j # Driver Code if __name__ =='__main__': # Maximum capacity of binary tree parent = [0 for i in range(MAX)] # Root marked parent[20] = -1 insertAdj(parent, 8, 20) insertAdj(parent, 22, 20) insertAdj(parent, 4, 8) insertAdj(parent, 12, 8) insertAdj(parent, 10, 12) insertAdj(parent, 14, 12) print(findLCA(10, 14, parent)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find LCA in a tree represented
// as parent array.
using System;
class GFG
{
// Maximum value in a node
static int MAX = 1000;
// Function to find the Lowest common ancestor
static int findLCA(int n1, int n2, int []parent)
{
// Create a visited vector and mark
// all nodes as not visited.
Boolean []visited = new Boolean[MAX];
visited[n1] = true;
// Moving from n1 node till root and
// mark every accessed node as visited
while (parent[n1] != -1)
{
visited[n1] = true;
// Move to the parent of node n1
n1 = parent[n1];
}
visited[n1] = true;
// For second node finding the first
// node common
while (!visited[n2])
n2 = parent[n2];
return n2;
}
// Insert function for Binary tree
static void insertAdj(int []parent, int i, int j)
{
parent[i] = j;
}
// Driver Code
public static void Main(String[] args)
{
// Maximum capacity of binary tree
int []parent = new int[MAX];
// Root marked
parent[20] = -1;
insertAdj(parent, 8, 20);
insertAdj(parent, 22, 20);
insertAdj(parent, 4, 8);
insertAdj(parent, 12, 8);
insertAdj(parent, 10, 12);
insertAdj(parent, 14, 12);
Console.WriteLine(findLCA(10, 14, parent));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find LCA in a tree represented
// as parent array.
// Maximum value in a node
const MAX = 1000;
// Function to find the Lowest common ancestor
function findLCA(n1, n2, parent) {
// Create a visited vector and mark
// all nodes as not visited.
let visited = new Array(MAX).fill(false);
visited[n1] = true;
// Moving from n1 node till root and
// mark every accessed node as visited
while (parent[n1] != -1) {
visited[n1] = true;
// Move to the parent of node n1
n1 = parent[n1];
}
visited[n1] = true;
// For second node finding the first
// node common
while (!visited[n2])
n2 = parent[n2];
return n2;
}
// Insert function for Binary tree
function insertAdj(parent, i, j) {
parent[i] = j;
}
// Driver Function
// Maximum capacity of binary tree
let parent = new Array(MAX);
// Root marked
parent[20] = -1;
insertAdj(parent, 8, 20);
insertAdj(parent, 22, 20);
insertAdj(parent, 4, 8);
insertAdj(parent, 12, 8);
insertAdj(parent, 10, 12);
insertAdj(parent, 14, 12);
document.write(findLCA(10, 14, parent));
// This code is contributed by _saurabh_jaiswal.
</script>
Complejidad de tiempo: la complejidad de tiempo del algoritmo anterior es O (log n) ya que requiere O (log n) tiempo en la búsqueda.