Dado un árbol binario con
como su raíz y para cualquier padre
su hijo izquierdo será 2*i y su hijo derecho será 2*i+1 . La tarea es encontrar la distancia mínima entre dos Nodes n1 y n2 .
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
. . . . . . . .
Ejemplos :
Input : n1 = 7, n2 = 10 Output : 5 Input : n1 = 6, n2 = 7 Output : 4
Hay tantas maneras de encontrar la distancia mínima entre dos Nodes dados de un árbol binario .
Aquí hay una forma eficiente de encontrar lo mismo con la ayuda de la representación binaria de Nodes dados. Para cualquier Node, eche un vistazo más de cerca a su representación binaria. Por ejemplo, considere el Node 9 . La representación binaria de 9 es 1001 . Entonces, para encontrar la ruta desde la raíz hasta un Node, encuentre la representación binaria de ese Node y muévase de izquierda a derecha en esa representación binaria y muévase al niño derecho en el árbol si se encuentra un 1 y muévase al niño izquierdo si se encuentra un 0 .
Path of 9 as per bit representation
1
/ \
2 3
/\ /\
4 5 6 7
/\
8 9.
Por lo tanto, para encontrar la distancia mínima entre dos Nodes, intentaremos encontrar la parte común de la representación binaria de ambos Nodes, que en realidad es la ruta común desde la raíz hasta el LCA. Deje que los primeros bits k para ambos Nodes sean iguales. Además, si la forma binaria es de n bits, muestra que la distancia de la ruta desde la raíz hasta ese Node es de n longitud. Por lo tanto, de las declaraciones anteriores podemos concluir fácilmente que: si m y n son la longitud de bit de dos Nodes y los k bits iniciales del valor de ambos Nodes son iguales, entonces la distancia mínima entre ambos Nodes será: m + n – 2* k .
Nota: El último bit similar muestra la posición de LCA en el árbol binario dado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find minimum distance between
// two nodes in binary tree
#include <bits/stdc++.h>
using namespace std;
// Function to get minimum path distance
int minDistance(int n1, int n2)
{
/** find the 1st dis-similar bit **/
// count bit length of n1 and n2
int bitCount1 = floor(log2(n1)) + 1;
int bitCount2 = floor(log2(n2)) + 1;
// find bit difference and maxBit
int bitDiff = abs(bitCount1 - bitCount2);
int maxBitCount = max(bitCount1, bitCount2);
if (bitCount1 > bitCount2) {
n2 = n2 * pow(2, bitDiff);
}
else {
n1 = n1 * pow(2, bitDiff);
}
int xorValue = n1 ^ n2;
int bitCountXorValue;
if( xorValue == 0)
bitCountXorValue = 1;
else
{
bitCountXorValue = floor(log2(xorValue)) + 1;
}
int disSimilarBitPosition = maxBitCount -
bitCountXorValue;
// calculate result by formula
int result = bitCount1 + bitCount2 -
2 * disSimilarBitPosition;
return result;
}
// Driver program
int main()
{
int n1 = 12, n2 = 5;
cout << minDistance(n1, n2);
return 0;
}
Java
// Java program to find minimum distance between
// two nodes in binary tree
import java.util.*;
class GFG
{
// Function to get minimum path distance
static int minDistance(int n1, int n2)
{
/** find the 1st dis-similar bit **/
// count bit length of n1 and n2
int bitCount1 =(int) Math.floor((Math.log(n1) /
Math.log(2))) + 1;
int bitCount2 = (int)Math.floor((Math.log(n2) /
Math.log(2))) + 1;
// find bit difference and maxBit
int bitDiff = Math.abs(bitCount1 - bitCount2);
int maxBitCount = Math.max(bitCount1, bitCount2);
if (bitCount1 > bitCount2)
{
n2 = n2 *(int) Math.pow(2, bitDiff);
}
else
{
n1 = n1 *(int) Math.pow(2, bitDiff);
}
int xorValue = n1 ^ n2;
int bitCountXorValue;
if( xorValue == 0)
bitCountXorValue = 1;
else
{
bitCountXorValue = (int)Math.floor((Math.log(xorValue) /
Math.log(2))) + 1;
}
int disSimilarBitPosition = maxBitCount -
bitCountXorValue;
// calculate result by formula
int result = bitCount1 + bitCount2 - 2 * disSimilarBitPosition;
return result;
}
// Driver program
public static void main(String args[])
{
int n1 = 12, n2 = 5;
System.out.println(minDistance(n1, n2));
}
}
// This code is contributed by
// Sanjit_Prasad
Python3
# Python 3 program to find minimum distance # between two nodes in binary tree from math import log2 # Function to get minimum path distance def minDistance(n1, n2): # find the 1st dis-similar bit # count bit length of n1 and n2 bitCount1 = int(log2(n1)) + 1 bitCount2 = int(log2(n2)) + 1 # find bit difference and maxBit bitDiff = abs(bitCount1 - bitCount2) maxBitCount = max(bitCount1, bitCount2) if (bitCount1 > bitCount2): n2 = int(n2 * pow(2, bitDiff)) else: n1 = int(n1 * pow(2, bitDiff)) xorValue = n1 ^ n2 if xorValue == 0: bitCountXorValue = 1 else: bitCountXorValue = int(log2(xorValue)) + 1 disSimilarBitPosition = (maxBitCount - bitCountXorValue) # calculate result by formula result = (bitCount1 + bitCount2 - 2 * disSimilarBitPosition) return result # Driver Code if __name__ == '__main__': n1 = 12 n2 = 5 print(minDistance(n1, n2)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find minimum distance between
// two nodes in binary tree
using System;
class GFG
{
// Function to get minimum path distance
static int minDistance(int n1, int n2)
{
/** find the 1st dis-similar bit **/
// count bit length of n1 and n2
int bitCount1 =(int) Math.Floor((Math.Log(n1) /
Math.Log(2))) + 1;
int bitCount2 = (int)Math.Floor((Math.Log(n2) /
Math.Log(2))) + 1;
// find bit difference and maxBit
int bitDiff = Math.Abs(bitCount1 - bitCount2);
int maxBitCount = Math.Max(bitCount1, bitCount2);
if (bitCount1 > bitCount2)
{
n2 = n2 *(int) Math.Pow(2, bitDiff);
}
else
{
n1 = n1 *(int) Math.Pow(2, bitDiff);
}
int xorValue = n1 ^ n2;
int bitCountXorValue;
if( xorValue == 0)
bitCountXorValue = 1;
else
{
bitCountXorValue = (int)Math.Floor((Math.Log(xorValue) /
Math.Log(2))) + 1;
}
int disSimilarBitPosition = maxBitCount - bitCountXorValue;
// calculate result by formula
int result = bitCount1 + bitCount2 - 2 * disSimilarBitPosition;
return result;
}
// Driver code
public static void Main(String []args)
{
int n1 = 12, n2 = 5;
Console.WriteLine(minDistance(n1, n2));
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// PHP program to find minimum distance
// between two nodes in binary tree
// Function to get minimum path distance
function minDistance($n1, $n2)
{
/** find the 1st dis-similar bit **/
// count bit length of n1 and n2
$bitCount1 = floor(log($n1, 2)) + 1;
$bitCount2 = floor(log($n2, 2)) + 1;
// find bit difference and maxBit
$bitDiff = abs($bitCount1 - $bitCount2);
$maxBitCount = max($bitCount1, $bitCount2);
if ($bitCount1 > $bitCount2)
{
$n2 = $n2 * pow(2, $bitDiff);
}
else
{
$n1 = $n1 * pow(2, $bitDiff);
}
$xorValue = $n1 ^ $n2;
$bitCountXorValue = floor(log($xorValue, 2)) + 1;
$disSimilarBitPosition = $maxBitCount -
$bitCountXorValue;
// calculate result by formula
$result = $bitCount1 + $bitCount2 - 2 *
$disSimilarBitPosition;
return $result;
}
// Driver Code
$n1 = 12;
$n2 = 5;
echo minDistance($n1, $n2);
// This code is contributed by akt_mit
?>
Javascript
<script>
// Javascript program to find minimum distance between
// two nodes in binary tree
// Function to get minimum path distance
function minDistance(n1, n2)
{
/** find the 1st dis-similar bit **/
// count bit length of n1 and n2
var bitCount1 = Math.floor(Math.log2(n1)) + 1;
var bitCount2 = Math.floor(Math.log2(n2)) + 1;
// find bit difference and maxBit
var bitDiff = Math.abs(bitCount1 - bitCount2);
var maxBitCount = Math.max(bitCount1, bitCount2);
if (bitCount1 > bitCount2) {
n2 = n2 * Math.pow(2, bitDiff);
}
else {
n1 = n1 * Math.pow(2, bitDiff);
}
var xorValue = n1 ^ n2;
var bitCountXorValue;
if( xorValue == 0)
bitCountXorValue = 1;
else
{
bitCountXorValue = Math.floor(Math.log2(xorValue)) + 1;
}
var disSimilarBitPosition = maxBitCount -
bitCountXorValue;
// calculate result by formula
var result = bitCount1 + bitCount2 -
2 * disSimilarBitPosition;
return result;
}
// Driver program
var n1 = 12, n2 = 5;
document.write( minDistance(n1, n2));
</script>
5
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA