Dados los valores de dos valores n1 y n2 en un árbol de búsqueda binaria, encuentre el antepasado común más bajo (LCA). Puede suponer que ambos valores existen en el árbol.
Ejemplos:
C++
// A recursive CPP program to find
// LCA of two nodes n1 and n2.
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node* left, *right;
};
/* Function to find LCA of n1 and n2.
The function assumes that both
n1 and n2 are present in BST */
node *lca(node* root, int n1, int n2)
{
if (root == NULL) return NULL;
// If both n1 and n2 are smaller
// than root, then LCA lies in left
if (root->data > n1 && root->data > n2)
return lca(root->left, n1, n2);
// If both n1 and n2 are greater than
// root, then LCA lies in right
if (root->data < n1 && root->data < n2)
return lca(root->right, n1, n2);
return root;
}
/* Helper function that allocates
a new node with the given data.*/
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = Node->right = NULL;
return(Node);
}
/* Driver code*/
int main()
{
// Let us construct the BST
// shown in the above figure
node *root = newNode(20);
root->left = newNode(8);
root->right = newNode(22);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
int n1 = 10, n2 = 14;
node *t = lca(root, n1, n2);
cout << "LCA of " << n1 << " and " << n2 << " is " << t->data<<endl;
n1 = 14, n2 = 8;
t = lca(root, n1, n2);
cout<<"LCA of " << n1 << " and " << n2 << " is " << t->data << endl;
n1 = 10, n2 = 22;
t = lca(root, n1, n2);
cout << "LCA of " << n1 << " and " << n2 << " is " << t->data << endl;
return 0;
}
// This code is contributed by rathbhupendra
C
// A recursive C program to find LCA of two nodes n1 and n2.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left, *right;
};
/* Function to find LCA of n1 and n2. The function assumes that both
n1 and n2 are present in BST */
struct node *lca(struct node* root, int n1, int n2)
{
if (root == NULL) return NULL;
// If both n1 and n2 are smaller than root, then LCA lies in left
if (root->data > n1 && root->data > n2)
return lca(root->left, n1, n2);
// If both n1 and n2 are greater than root, then LCA lies in right
if (root->data < n1 && root->data < n2)
return lca(root->right, n1, n2);
return root;
}
/* Helper function that allocates a new node with the given data.*/
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = node->right = NULL;
return(node);
}
/* Driver program to test lca() */
int main()
{
// Let us construct the BST shown in the above figure
struct node *root = newNode(20);
root->left = newNode(8);
root->right = newNode(22);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
int n1 = 10, n2 = 14;
struct node *t = lca(root, n1, n2);
printf("LCA of %d and %d is %d \n", n1, n2, t->data);
n1 = 14, n2 = 8;
t = lca(root, n1, n2);
printf("LCA of %d and %d is %d \n", n1, n2, t->data);
n1 = 10, n2 = 22;
t = lca(root, n1, n2);
printf("LCA of %d and %d is %d \n", n1, n2, t->data);
getchar();
return 0;
}
Java
// Recursive Java program to print lca of two nodes
// A binary tree node
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
/* Function to find LCA of n1 and n2. The function assumes that both
n1 and n2 are present in BST */
Node lca(Node node, int n1, int n2)
{
if (node == null)
return null;
// If both n1 and n2 are smaller than root, then LCA lies in left
if (node.data > n1 && node.data > n2)
return lca(node.left, n1, n2);
// If both n1 and n2 are greater than root, then LCA lies in right
if (node.data < n1 && node.data < n2)
return lca(node.right, n1, n2);
return node;
}
/* Driver program to test lca() */
public static void main(String args[])
{
// Let us construct the BST shown in the above figure
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(8);
tree.root.right = new Node(22);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(12);
tree.root.left.right.left = new Node(10);
tree.root.left.right.right = new Node(14);
int n1 = 10, n2 = 14;
Node t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
n1 = 14;
n2 = 8;
t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
n1 = 10;
n2 = 22;
t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# A recursive python program to find LCA of two nodes
# n1 and n2
# A Binary tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to find LCA of n1 and n2. The function assumes
# that both n1 and n2 are present in BST
def lca(root, n1, n2):
# Base Case
if root is None:
return None
# If both n1 and n2 are smaller than root, then LCA
# lies in left
if(root.data > n1 and root.data > n2):
return lca(root.left, n1, n2)
# If both n1 and n2 are greater than root, then LCA
# lies in right
if(root.data < n1 and root.data < n2):
return lca(root.right, n1, n2)
return root
# Driver program to test above function
# Let us construct the BST shown in the figure
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
n1 = 10 ; n2 = 14
t = lca(root, n1, n2)
print ("LCA of %d and %d is %d" %(n1, n2, t.data))
n1 = 14 ; n2 = 8
t = lca(root, n1, n2)
print ("LCA of %d and %d is %d" %(n1, n2 , t.data))
n1 = 10 ; n2 = 22
t = lca(root, n1, n2)
print ("LCA of %d and %d is %d" %(n1, n2, t.data))
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
using System;
// Recursive C# program to print lca of two nodes
// A binary tree node
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
public Node root;
/* Function to find LCA of n1 and n2. The function assumes that both
n1 and n2 are present in BST */
public virtual Node lca(Node node, int n1, int n2)
{
if (node == null)
{
return null;
}
// If both n1 and n2 are smaller than root, then LCA lies in left
if (node.data > n1 && node.data > n2)
{
return lca(node.left, n1, n2);
}
// If both n1 and n2 are greater than root, then LCA lies in right
if (node.data < n1 && node.data < n2)
{
return lca(node.right, n1, n2);
}
return node;
}
/* Driver program to test lca() */
public static void Main(string[] args)
{
// Let us construct the BST shown in the above figure
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(8);
tree.root.right = new Node(22);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(12);
tree.root.left.right.left = new Node(10);
tree.root.left.right.right = new Node(14);
int n1 = 10, n2 = 14;
Node t = tree.lca(tree.root, n1, n2);
Console.WriteLine("LCA of " + n1 + " and " + n2 + " is " + t.data);
n1 = 14;
n2 = 8;
t = tree.lca(tree.root, n1, n2);
Console.WriteLine("LCA of " + n1 + " and " + n2 + " is " + t.data);
n1 = 10;
n2 = 22;
t = tree.lca(tree.root, n1, n2);
Console.WriteLine("LCA of " + n1 + " and " + n2 + " is " + t.data);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Recursive JavaScript program to print lca of two nodes
// A binary tree node
class Node
{
constructor(item)
{
this.data=item;
this.left=this.right=null;
}
}
let root;
function lca(node,n1,n2)
{
if (node == null)
return null;
// If both n1 and n2 are smaller than root,
// then LCA lies in left
if (node.data > n1 && node.data > n2)
return lca(node.left, n1, n2);
// If both n1 and n2 are greater than root,
// then LCA lies in right
if (node.data < n1 && node.data < n2)
return lca(node.right, n1, n2);
return node;
}
/* Driver program to test lca() */
// Let us construct the BST shown in the above figure
root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
let n1 = 10, n2 = 14;
let t = lca(root, n1, n2);
document.write("LCA of " + n1 + " and " + n2 + " is " +
t.data+"<br>");
n1 = 14;
n2 = 8;
t = lca(root, n1, n2);
document.write("LCA of " + n1 + " and " + n2 + " is " +
t.data+"<br>");
n1 = 10;
n2 = 22;
t = lca(root, n1, n2);
document.write("LCA of " + n1 + " and " + n2 + " is " +
t.data+"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
C++
// A recursive CPP program to find
// LCA of two nodes n1 and n2.
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node* left, *right;
};
/* Function to find LCA of n1 and n2.
The function assumes that both n1 and n2
are present in BST */
node *lca(node* root, int n1, int n2)
{
while (root != NULL)
{
// If both n1 and n2 are smaller than root,
// then LCA lies in left
if (root->data > n1 && root->data > n2)
root = root->left;
// If both n1 and n2 are greater than root,
// then LCA lies in right
else if (root->data < n1 && root->data < n2)
root = root->right;
else break;
}
return root;
}
/* Helper function that allocates
a new node with the given data.*/
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = Node->right = NULL;
return(Node);
}
/* Driver code*/
int main()
{
// Let us construct the BST
// shown in the above figure
node *root = newNode(20);
root->left = newNode(8);
root->right = newNode(22);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
int n1 = 10, n2 = 14;
node *t = lca(root, n1, n2);
cout << "LCA of " << n1 << " and " << n2 << " is " << t->data<<endl;
n1 = 14, n2 = 8;
t = lca(root, n1, n2);
cout<<"LCA of " << n1 << " and " << n2 << " is " << t->data << endl;
n1 = 10, n2 = 22;
t = lca(root, n1, n2);
cout << "LCA of " << n1 << " and " << n2 << " is " << t->data << endl;
return 0;
}
// This code is contributed by rathbhupendra
C
// A recursive C program to find LCA of two nodes n1 and n2.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* left, *right;
};
/* Function to find LCA of n1 and n2. The function assumes that both
n1 and n2 are present in BST */
struct node *lca(struct node* root, int n1, int n2)
{
while (root != NULL)
{
// If both n1 and n2 are smaller than root, then LCA lies in left
if (root->data > n1 && root->data > n2)
root = root->left;
// If both n1 and n2 are greater than root, then LCA lies in right
else if (root->data < n1 && root->data < n2)
root = root->right;
else break;
}
return root;
}
/* Helper function that allocates a new node with the given data.*/
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = node->right = NULL;
return(node);
}
/* Driver program to test lca() */
int main()
{
// Let us construct the BST shown in the above figure
struct node *root = newNode(20);
root->left = newNode(8);
root->right = newNode(22);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
int n1 = 10, n2 = 14;
struct node *t = lca(root, n1, n2);
printf("LCA of %d and %d is %d \n", n1, n2, t->data);
n1 = 14, n2 = 8;
t = lca(root, n1, n2);
printf("LCA of %d and %d is %d \n", n1, n2, t->data);
n1 = 10, n2 = 22;
t = lca(root, n1, n2);
printf("LCA of %d and %d is %d \n", n1, n2, t->data);
getchar();
return 0;
}
Java
// Recursive Java program to print lca of two nodes
// A binary tree node
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
/* Function to find LCA of n1 and n2.
The function assumes that both
n1 and n2 are present in BST */
static Node lca(Node root, int n1, int n2)
{
while (root != null)
{
// If both n1 and n2 are smaller
// than root, then LCA lies in left
if (root.data > n1 &&
root.data > n2)
root = root.left;
// If both n1 and n2 are greater
// than root, then LCA lies in right
else if (root.data < n1 &&
root.data < n2)
root = root.right;
else break;
}
return root;
}
/* Driver program to test lca() */
public static void main(String args[])
{
// Let us construct the BST shown in the above figure
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(8);
tree.root.right = new Node(22);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(12);
tree.root.left.right.left = new Node(10);
tree.root.left.right.right = new Node(14);
int n1 = 10, n2 = 14;
Node t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
n1 = 14;
n2 = 8;
t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
n1 = 10;
n2 = 22;
t = tree.lca(tree.root, n1, n2);
System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);
}
}
// This code is contributed by SHUBHAMSINGH10
Python3
# A recursive python program to find LCA of two nodes
# n1 and n2
# A Binary tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to find LCA of n1 and n2.
# The function assumes that both
# n1 and n2 are present in BST
def lca(root, n1, n2):
while root:
# If both n1 and n2 are smaller than root,
# then LCA lies in left
if root.data > n1 and root.data > n2:
root = root.left
# If both n1 and n2 are greater than root,
# then LCA lies in right
elif root.data < n1 and root.data < n2:
root = root.right
else:
break
return root
# Driver program to test above function
# Let us construct the BST shown in the figure
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
n1 = 10 ; n2 = 14
t = lca(root, n1, n2)
print ("LCA of %d and %d is %d" %(n1, n2, t.data))
n1 = 14 ; n2 = 8
t = lca(root, n1, n2)
print ("LCA of %d and %d is %d" %(n1, n2 , t.data))
n1 = 10 ; n2 = 22
t = lca(root, n1, n2)
print ("LCA of %d and %d is %d" %(n1, n2, t.data))
# This Code is Contributed by Sumit Bhardwaj (Timus)
C#
using System;
// Recursive C# program to print lca of two nodes
// A binary tree node
public class Node
{
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class BinaryTree
{
public Node root;
/* Function to find LCA of n1 and n2.
The function assumes that both
n1 and n2 are present in BST */
public virtual Node lca(Node root, int n1, int n2)
{
while (root != null)
{
// If both n1 and n2 are smaller than
// root, then LCA lies in left
if (root.data > n1 && root.data > n2)
root = root.left;
// If both n1 and n2 are greater than
// root, then LCA lies in right
else if (root.data < n1 && root.data < n2)
root = root.right;
else break;
}
return root;
}
/* Driver program to test lca() */
public static void Main(string[] args)
{
// Let us construct the BST shown in the above figure
BinaryTree tree = new BinaryTree();
tree.root = new Node(20);
tree.root.left = new Node(8);
tree.root.right = new Node(22);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(12);
tree.root.left.right.left = new Node(10);
tree.root.left.right.right = new Node(14);
int n1 = 10, n2 = 14;
Node t = tree.lca(tree.root, n1, n2);
Console.WriteLine(
"LCA of " + n1 + " and " + n2
+ " is " + t.data);
n1 = 14;
n2 = 8;
t = tree.lca(tree.root, n1, n2);
Console.WriteLine(
"LCA of " + n1 + " and " + n2
+ " is " + t.data);
n1 = 10;
n2 = 22;
t = tree.lca(tree.root, n1, n2);
Console.WriteLine(
"LCA of " + n1 + " and " + n2
+ " is " + t.data);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Recursive Javascript program to
// print lca of two nodes
// A binary tree node
class Node
{
constructor(item)
{
this.data = item;
this.left = null;
this.right = null;
}
}
var root = null;
/* Function to find LCA of n1 and n2.
The function assumes that both
n1 and n2 are present in BST */
function lca(root, n1, n2)
{
while (root != null)
{
// If both n1 and n2 are smaller than
// root, then LCA lies in left
if (root.data > n1 && root.data > n2)
root = root.left;
// If both n1 and n2 are greater than
// root, then LCA lies in right
else if (root.data < n1 && root.data < n2)
root = root.right;
else break;
}
return root;
}
// Driver code
// Let us construct the BST shown
// in the above figure
root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
var n1 = 10, n2 = 14;
var t = lca(root, n1, n2);
document.write("LCA of " + n1 + " and " + n2 +
" is " + t.data + "<br>");
n1 = 14;
n2 = 8;
t = lca(root, n1, n2);
document.write("LCA of " + n1 + " and " + n2 +
" is " + t.data+ "<br>");
n1 = 10;
n2 = 22;
t = lca(root, n1, n2);
document.write("LCA of " + n1 + " and " + n2 +
" is " + t.data+ "<br>");
// This code is contributed by rrrtnx
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA