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

01.01.2020Деревья

Данный массив представляет дерево таким образом, что значение массива дает родительский узел этого конкретного индекса. Значение индекса корневого узла всегда будет равно -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 ² ), так как мы должны линейно искать каждый узел.

Эффективное решение может решить вышеупомянутую проблему за 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