Рубрики

Найти высоту двоичного дерева, представленного родительским массивом

Данный массив представляет дерево таким образом, что значение массива дает родительский узел этого конкретного индекса. Значение индекса корневого узла всегда будет равно -1. Найдите высоту дерева.
Высота бинарного дерева — это число узлов на пути от корня к самому глубокому листовому узлу, в число которых входят как корень, так и лист.

Input: parent[] = {1 5 5 2 2 -1 3}
Output: 4
The given array represents following Binary Tree 
         5
        /  \
       1    2
      /    / \
     0    3   4
         /
        6 


Input: parent[] = {-1, 0, 0, 1, 1, 3, 5};
Output: 5
The given array represents following Binary Tree 
         0
       /   \
      1     2
     / \
    3   4
   /
  5 
 /
6

Источник: Amazon Интервью опыт | Установите 128 (для SDET)

Мы настоятельно рекомендуем свернуть ваш браузер и попробовать это в первую очередь.

Простое решение состоит в том, чтобы сначала построить дерево, а затем найти высоту построенного бинарного дерева. Дерево может быть построено рекурсивно, сначала просматривая текущий корень, затем повторяя найденные индексы и делая их левым и правым поддеревьями корня. Это решение принимает O (n 2 ), так как мы должны линейно искать каждый узел.

Эффективное решение может решить вышеупомянутую проблему за O (n) время. Идея состоит в том, чтобы сначала вычислить глубину каждого узла и сохранить в глубину массива []. Как только у нас есть глубина всех узлов, мы возвращаем максимум всех глубин.
1) Найти глубину всех узлов и заполнить вспомогательный массив глубиной [].
2) Вернуть максимальное значение в глубину [].

Ниже приведены шаги для определения глубины узла по индексу i.
1) Если это корень, глубина [i] равна 1.
2) Если оценивается глубина родителя [i], глубина [i] равна глубине [parent [i]] + 1.
3) Если глубина parent [i] не оценивается, повторите процедуру для parent и присвойте глубину [i] в качестве глубины [parent [i]] + 1 (аналогично описанному выше).

Ниже приводится реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска высоты с использованием родительского массива
#include <iostream>

using namespace std;

  
// Эта функция заполняет глубину i-го элемента в parent []. Глубина
// заполнено в глубину [i].

void fillDepth(int parent[], int i, int depth[])

{

    // Если глубина [i] уже заполнена

    if (depth[i])

        return;

  

    // Если узел с индексом i является корневым

    if (parent[i] == -1)

    {

        depth[i] = 1;

        return;

    }

  

    // Если глубина родителя не была оценена ранее, тогда вычисляем

    // глубина родителя первая

    if (depth[parent[i]] == 0)

        fillDepth(parent, parent[i], depth);

  

    // Глубина этого узла - глубина родителя плюс 1

    depth[i] = depth[parent[i]]  + 1;

}

  
// Эта функция возвращает высоту двоичного дерева, представленного
// родительский массив

int findHeight(int parent[], int n)

{

    // Создать массив для хранения глубины всех узлов / и

    // инициализируем глубину каждого узла как 0 (неверный

    // значение). Глубина корня 1

    int depth[n];

    for (int i = 0; i < n; i++)

        depth[i] = 0;

  

    // заполняем глубину всех узлов

    for (int i = 0; i < n; i++)

        fillDepth(parent, i, depth);

  

    // Высота бинарного дерева максимальна для всех глубин.

    // Находим максимальное значение в глубине [] и присваиваем его ht.

    int ht = depth[0];

    for (int i=1; i<n; i++)

        if (ht < depth[i])

            ht = depth[i];

    return ht;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // int parent [] = {1, 5, 5, 2, 2, -1, 3};

    int parent[] = {-1, 0, 0, 1, 1, 3, 5};

  

    int n = sizeof(parent)/sizeof(parent[0]);

    cout << "Height is " << findHeight(parent, n);

    return 0;

}

Джава

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

class BinaryTree {

  

    // Эта функция заполняет глубину i-го элемента в parent []. Глубина

    // заполнено в глубину [i].

    void fillDepth(int parent[], int i, int depth[]) {

  

        // Если глубина [i] уже заполнена

        if (depth[i] != 0) {

            return;

        }

  

        // Если узел с индексом i является корневым

        if (parent[i] == -1) {

            depth[i] = 1;

            return;

        }

  

        // Если глубина родителя не была оценена ранее, тогда вычисляем

        // глубина родителя первая

        if (depth[parent[i]] == 0) {

            fillDepth(parent, parent[i], depth);

        }

  

        // Глубина этого узла - глубина родителя плюс 1

        depth[i] = depth[parent[i]] + 1;

    }

  

    // Эта функция возвращает высоту двоичного дерева, представленного

    // родительский массив

    int findHeight(int parent[], int n) {

          

        // Создать массив для хранения глубины всех узлов / и

        // инициализируем глубину каждого узла как 0 (неверный

        // значение). Глубина корня 1

        int depth[] = new int[n];

        for (int i = 0; i < n; i++) {

            depth[i] = 0;

        }

  

        // заполняем глубину всех узлов

        for (int i = 0; i < n; i++) {

            fillDepth(parent, i, depth);

        }

  

        // Высота бинарного дерева максимальна для всех глубин.

        // Находим максимальное значение в глубине [] и присваиваем его ht.

        int ht = depth[0];

        for (int i = 1; i < n; i++) {

            if (ht < depth[i]) {

                ht = depth[i];

            }

        }

        return ht;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[]) {

  

        BinaryTree tree = new BinaryTree();

  

        // int parent [] = {1, 5, 5, 2, 2, -1, 3};

        int parent[] = new int[]{-1, 0, 0, 1, 1, 3, 5};

  

        int n = parent.length;

        System.out.println("Height is  " + tree.findHeight(parent, n));

    }

}

питон

# Программа Python для определения высоты с использованием родительского массива

  
# Эта функция заполняет глубину i-го элемента в parent []
# Глубина заполняется в глубину [я]

  

def fillDepth(parent, i , depth):

      

    # Если глубина [i] уже заполнена

    if depth[i] != 0:

        return 

      

    # Если узел с индексом i является корневым

    if parent[i] == -1:

        depth[i] = 1

        return 

  

    # Если глубина родителя не была оценена ранее,

    # сначала оцените глубину родительского

    if depth[parent[i]] == 0:

        fillDepth(parent, parent[i] , depth)

  

    # Глубина этого узла - глубина родителя плюс 1

    depth[i] = depth[parent[i]] + 1

  
# Эта функция возвращает высоту представленного двоичного дерева
# по родительскому массиву

def findHeight(parent):

    n = len(parent)  

    # Создайте массив для хранения глубины всех узлов и

    # инициализировать глубину каждого узла как 0

    # Глубина корня равна 1

    depth = [0 for i in range(n)]

  

    # заполняем глубину всех узлов

    for i in range(n):

        fillDepth(parent, i, depth)

  

    # Высота бинарного дерева максимальна

    # глубины. Найти максимум по глубине [] и назначить

    # это к хт

    ht = depth[0]

    for i in range(1,n):

        ht = max(ht, depth[i])

  

    return ht

  
# Программа драйвера для проверки вышеуказанной функции

parent = [-1 , 0 , 0 , 1 , 1 , 3 , 5]

print "Height is %d" %(findHeight(parent))

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

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

public class BinaryTree

{

  

    // Эта функция заполняет глубину i-го элемента в parent []. Глубина

    // заполнено в глубину [i].

    public virtual void fillDepth(int[] parent, int i, int[] depth)

    {

  

        // Если глубина [i] уже заполнена

        if (depth[i] != 0)

        {

            return;

        }

  

        // Если узел с индексом i является корневым

        if (parent[i] == -1)

        {

            depth[i] = 1;

            return;

        }

  

        // Если глубина родителя не была оценена ранее, тогда вычисляем

        // глубина родителя первая

        if (depth[parent[i]] == 0)

        {

            fillDepth(parent, parent[i], depth);

        }

  

        // Глубина этого узла - глубина родителя плюс 1

        depth[i] = depth[parent[i]] + 1;

    }

  

    // Эта функция возвращает высоту двоичного дерева, представленного

    // родительский массив

    public virtual int findHeight(int[] parent, int n)

    {

  

        // Создать массив для хранения глубины всех узлов / и

        // инициализируем глубину каждого узла как 0 (неверный

        // значение). Глубина корня 1

        int[] depth = new int[n];

        for (int i = 0; i < n; i++)

        {

            depth[i] = 0;

        }

  

        // заполняем глубину всех узлов

        for (int i = 0; i < n; i++)

        {

            fillDepth(parent, i, depth);

        }

  

        // Высота бинарного дерева максимальна для всех глубин.

        // Находим максимальное значение в глубине [] и присваиваем его ht.

        int ht = depth[0];

        for (int i = 1; i < n; i++)

        {

            if (ht < depth[i])

            {

                ht = depth[i];

            }

        }

        return ht;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main(string[] args)

    {

  

        BinaryTree tree = new BinaryTree();

  

        // int parent [] = {1, 5, 5, 2, 2, -1, 3};

        int[] parent = new int[]{-1, 0, 0, 1, 1, 3, 5};

  

        int n = parent.Length;

        Console.WriteLine("Height is  " + tree.findHeight(parent, n));

    }

}

  

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


Выход:

Height is 5

Обратите внимание, что временная сложность этих программ кажется больше, чем O (n). Если мы посмотрим поближе, то увидим, что глубина каждого узла оценивается только один раз.

Эта статья предоставлена Сиддхартом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Найти высоту двоичного дерева, представленного родительским массивом

0.00 (0%) 0 votes