Рубрики

Расстояние между двумя узлами двоичного дерева со значениями узлов от 1 до N

Дано двоичное дерево с как его корень и для любого родителя его левый ребенок будет 2 * i, а правый ребенок будет 2 * i + 1 . Задача — найти минимальное расстояние между двумя узлами n1 и n2 .

           
               1
            /      \
           2        3
         /  \      / \
        4    5    6   7
      /  \  / \  / \ / \
     .  .  .  . .  .  .  . 

Примеры :

Input : n1 = 7, n2 = 10
Output : 5

Input : n1 = 6, n2 = 7
Output : 4

Существует так много способов найти минимальное расстояние между двумя заданными узлами двоичного дерева .

Вот эффективный способ найти то же самое с помощью двоичного представления данных узлов. Для любого узла более подробно рассмотрим его двоичное представление. Например, рассмотрим узел 9 . Двоичное представление 9 — 1001 . Таким образом, чтобы найти путь от корня к узлу, найдите двоичное представление этого узла и переместитесь слева направо в этом двоичном представлении и переместитесь к правому дочернему элементу в дереве, если встречается 1, и перейдите к левому дочернему элементу, если встречается 0 ,

Path of 9 as per bit representation
        1
       / \
      2   3
     /\   /\
    4  5 6  7
   /\ 
  8  9.

Следовательно, для нахождения минимального расстояния между двумя узлами мы попытаемся найти общую часть двоичного представления обоих узлов, которая фактически является общим путем от корня до LCA. Пусть первые k-биты для обоих узлов одинаковы. Кроме того, если двоичная форма имеет n-бит, то это показывает, что расстояние пути от корня до этого узла имеет длину n. Следовательно, из приведенных выше утверждений мы можем легко сделать вывод, что: если m и n — длина в битах двух узлов и k-начальные биты значения обоих узлов одинаковы, то минимальное расстояние между обоими узлами будет: m + n — 2 * k ,

Примечание. Последний аналогичный бит показывает положение LCA в данном двоичном дереве.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для поиска минимального расстояния между
// два узла в двоичном дереве

  
#include <bits/stdc++.h>

using namespace std;

  
// Функция для получения минимального расстояния пути

int minDistance(int n1, int n2)

{

    / ** найти 1-й несхожий бит ** /

    // посчитаем длину битов n1 и n2

    int bitCount1 = floor(log2(n1)) + 1;

    int bitCount2 = floor(log2(n2)) + 1;

  

    // найти битовую разницу и 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 = floor(log2(xorValue)) + 1;

    int disSimilarBitPosition = maxBitCount - bitCountXorValue;

  

    // вычисляем результат по формуле

    int result = bitCount1 + bitCount2 - 2 * disSimilarBitPosition;

    return result;

}

  
// Драйвер программы

int main()

{

    int n1 = 12, n2 = 5;

  

    cout << minDistance(n1, n2);

  

    return 0;

}

Джава

// Java программа для поиска минимального расстояния между
// два узла в двоичном дереве

import java.util.*;

  

class GFG

{

    // Функция для получения минимального расстояния пути

    static int minDistance(int n1, int n2)

    {

        /** find the 1st dis-similar bit **/

        // посчитаем длину битов n1 и 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;

  

        // найти битовую разницу и 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 = (int)Math.floor((Math.log(xorValue) /

                                Math.log(2))) + 1;

        int disSimilarBitPosition = maxBitCount - bitCountXorValue;

  

        // вычисляем результат по формуле

        int result = bitCount1 + bitCount2 - 2 * disSimilarBitPosition;

        return result;

    }

  

    // Драйвер программы

    public static void main(String args[])

    {

        int n1 = 12, n2 = 5;

        System.out.println(minDistance(n1, n2));

    }

}

  
// Этот код предоставлен
// Sanjit_Prasad

python3

# Python 3 программа для поиска минимального расстояния
# между двумя узлами в двоичном дереве

from math import floor, pow, log2

  
# Функция, чтобы получить минимальное расстояние пути

def minDistance(n1, n2):

      

    # найти 1-й несхожий бит

    количество битов n1 и n2

    bitCount1 = floor(log2(n1)) + 1

    bitCount2 = floor(log2(n2)) + 1

  

    # найти разницу в битах и 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

    bitCountXorValue = floor(log2(xorValue)) + 1

    disSimilarBitPosition = (maxBitCount - 

                             bitCountXorValue)

  

    # рассчитать результат по формуле

    result = (bitCount1 + bitCount2 - 2 *

                   disSimilarBitPosition)

    return result

  
Код водителя

if __name__ == '__main__':

    n1 = 12

    n2 = 5

  

    print(minDistance(n1, n2))

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # программа для поиска минимального расстояния между
// два узла в двоичном дереве

using System; 

      

class GFG

{

    // Функция для получения минимального расстояния пути

    static int minDistance(int n1, int n2)

    {

        / ** найти 1-й несхожий бит ** /

        // посчитаем длину битов n1 и 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;

  

        // найти битовую разницу и 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 = (int)Math.Floor((Math.Log(xorValue) /

                                Math.Log(2))) + 1;

        int disSimilarBitPosition = maxBitCount - bitCountXorValue;

  

        // вычисляем результат по формуле

        int result = bitCount1 + bitCount2 - 2 * disSimilarBitPosition;

        return result;

    }

  

    // Код драйвера

    public static void Main(String []args)

    {

        int n1 = 12, n2 = 5;

        Console.WriteLine(minDistance(n1, n2));

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

PHP

<?php
// PHP программа для поиска минимального расстояния
// между двумя узлами в двоичном дереве

  
// Функция для получения минимального расстояния пути

function minDistance($n1, $n2

    / ** найти 1-й несхожий бит ** /

    // посчитаем длину битов n1 и n2

    $bitCount1 = floor(log($n1, 2)) + 1; 

    $bitCount2 = floor(log($n2, 2)) + 1; 

  

    // найти битовую разницу и 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

  

    // вычисляем результат по формуле

    $result = $bitCount1 + $bitCount2 - 2 *

              $disSimilarBitPosition

    return $result

  
// Код драйвера

$n1 = 12;

$n2 = 5; 

  

echo minDistance($n1, $n2); 

  
// Этот код предоставлен akt_mit
?>

Выход:

5

Рекомендуемые посты:

Расстояние между двумя узлами двоичного дерева со значениями узлов от 1 до N

0.00 (0%) 0 votes