Минимальная глубина бинарного дерева

Как найти минимальную глубину двоичного дерева

Минимальная глубина двоичного дерева — это количество узлов от корневого узла до ближайшего листового узла.

Рассмотрим двоичное дерево ниже:

Минимальная глубина этого дерева составляет 3 3 3; он состоит из узлов 1, 2 и 4.

Давайте посмотрим на решения для вычисления минимальной глубины заданного двоичного дерева.

1. Рекурсивное решение

Идея состоит в том, чтобы проверить, является ли каждый узел листовым. Если текущий узел является листовым, вернуть 1 1 семантика> 1. В противном случае, если у узла нет левого поддерева, то он повторяется в правом поддереве. Точно так же, если узел не имеет правого поддерева, то повторяется в левом поддереве. Наконец, если у узла есть как левое, так и правое поддеревья, повторите для обоих и верните минимальное значение.

Реализация

Используя двоичное дерево, показанное выше, алгоритм реализуется следующим образом:

#include с использованием пространства имен std; struct Node value = val; this-> left = this-> right = NULL;>>; в t minimumDepth (Node * curr) left == NULL && curr-> right == NULL) return 1; //Текущий узел имеет только правое поддерево. если (! curr-> left) вернуть 1 + minimumDepth (curr-> right); //У текущего узла осталось только поддерево. иначе, если (! curr-> right) return 1 + minimumDepth (curr-> left); //если ни один из вышеперечисленных случаев, то повторяется как в левом, так и в правом поддеревьях. return 1 + min (minimumDepth (curr-> right), minimumDepth (curr-> left));>//код драйвера int main () left = новый узел (2); root-> right = новый узел (3); root-> left-> left = новый узел (4); root-> right-> left = новый узел (5); root-> right-> right = новый узел (6); root-> right-> right-> left = новый узел (8); root-> right-> left-> right = новый узел (7); cout

2. Решение обхода порядка уровней

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

Алгоритм можно оптимизировать дальше, используя идею, лежащую в основе порядка уровней обход. Прежде чем читать дальше, подумайте о том, как можно использовать обход по уровням для оптимизации вычисления минимальной глубины.

Источник

Минимальная глубина бинарного дерева в JavaScript

Структуры данных могут быть немного сложными, особенно для тех, у кого нет традиционной степени CS. Тем не менее, любой может улучшить их со временем и практикой. Сегодня я собираюсь показать, что вам нужно решить минимальную глубину двоичного дерева.

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

Давайте начнем, вы можете сделать это с помощью поиска в глубину или поиска в ширину. Я использую поиск в ширину, потому что хочу сначала посетить каждый узел на одном уровне. Вы можете сделать это рекурсивно с DFS, но это зависит от вас.

В BFS мы используем очередь. Очередь — это структура данных LIFO, которая поступает последним, мы хотим посетить узел и его дочерние элементы. Мы также хотим вести общий подсчет минимальной глубины. Мы начинаем с -1, потому что, когда мы выталкиваем корень, он становится равным нулю, глубина корня всегда равна нулю, мы не углублялись

function binary_tree_min_depth(root)

Теперь нам нужно выполнить итерацию в очереди и добавить дочерние узлы в очередь. и увеличьте промежуточную сумму, потому что, хотя в очереди есть узел, это означает, что в ней больше глубины

Теперь наступает встреча с кодом, нам нужно идти уровень за уровнем и получать дочерние элементы каждого поддерева.

let level = queue.length for(let i = 0; i < level; i++)< let node = queue.shift() //pop node off the queue //if there are no left and right children thats our mindepth if(!node.left && !node.right )< return minDepth >//if there are more nodes to left and right add to queue if(node.right !== null) < queue.push(node.right) >if(node.left !== null) < queue.push(node.left) >> >

После всего проделанного возвращаем minDepth

function binary_tree_min_depth(root) < // WRITE YOUR BRILLIANT CODE HERE let queue = [] queue.push(root) let minDepth = -1 while(queue.length >0) < minDepth++ let level = queue.length for(let i = 0; i < level; i++)< let node = queue.shift() if(!node.left && !node.right )< return minDepth >if(node.right !== null) < queue.push(node.right) >if(node.left !== null) < queue.push(node.left) >> > return minDepth >

Это! Вот как вы находите минимальную глубину двоичного дерева в Javascript.

Источник

Русские Блоги

Максимальная и минимальная глубина двоичного дерева

По заданному бинарному дереву найдите его максимальную глубину.

Глубина двоичного дерева — это количество узлов на самом длинном пути от корневого узла до самого дальнего конечного узла.

Объяснение: Конечный узел относится к узлу без дочерних узлов.

Пример:
Учитывая двоичное дерево [3,9,20, ноль, ноль, 15,7],

3
/ \
9 20
/ \
15 7
возвращает максимальную глубину 3.

Первое решение, о котором можно подумать, — это использовать рекурсию. После ее завершения я обнаружил, что большинство людей также используют рекурсивное мышление или косвенную рекурсию, но также итерационный метод. Просто запишите рекурсию.

class Solution < public: int maxDepth(TreeNode* root) < int L=0,R=0; if(root == NULL) return 0; else < L = maxDepth(root->left); R = maxDepth(root->right); return (L>R?L:R)+1; > > >;

Видел код, чрезвычайно сжатый в одну строку (Java)

class Solution < public: int maxDepth(TreeNode* root) < return (root==NULL)? 0:max(maxDepth(root->left),maxDepth(root->right))+1; > >; Автор: Ся-гу-жень-жень 

По заданному двоичному дереву найдите его минимальную глубину.

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

Объяснение: Конечный узел относится к узлу без дочерних узлов.

Дано двоичное дерево [3,9,20, нуль, ноль, 15,7],

3
/ \
9 20
/ \
15 7
возвращает минимальную глубину 2.

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

/** * Definition for a binary tree node. * struct TreeNode < * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) <>* >; */ class Solution < public: int minDepth(TreeNode* root) < int L=0,R=0; if(root == NULL) return 0; else < L = minDepth(root->left); R = minDepth(root->right); return (L > >;

Яма: Когда входным примером является [1,2], в соответствии с предыдущим пониманием значения вопроса генерируется одно дерево, и результатом должна быть высота меньшего из левого и правого поддеревьев +1, Но ожидаемый результат здесь равен 2. После рассмотрения вашей дискуссии смысл вопроса должен заключаться в том, что в этом случае минимальная высота одного дерева должна быть высотой дерева, а не высотой пустого поддерева + 1

class Solution < public: int minDepth(TreeNode* root) < int L=0,R=0; if(root == NULL) return 0; else < L = minDepth(root->left); R = minDepth(root->right); return (L&&R)?(L > >;

Время выполнения: 16 мс, победили 61,79% пользователей во всех представлениях C ++

Потребление памяти: 19,5 МБ, победили 86,14% пользователей во всех представлениях C ++

Источник

Русские Блоги

Бинарное дерево (6): максимальная и минимальная глубина бинарного дерева

Глубина и высота двоичного дерева

1. Глубина бинарного дерева

Для узла в двоичном дереве, этоГлубокий от корневого узла до узлаКоличество узлов, содержащихся в самом длинном простом пути, находится сверху вниз. Следовательно, глубина доступа к определенному узлуИспользуйте первое обход

2. Высота двоичного дерева

Для узла в двоичном деревеВысота от узела листа до узлаКоличество узлов, содержащихся в самом длинном простом пути, находится ниже к вышеуказанному. Итак, высота доступа к узлуИспользуйте последующее обход

3. Глубина и высота двоичного дерева

Глубина и высота каждого узла каждого слоя показаны на рисунке:

4. Глубина и высота двоичного дерева

Высота корневого узла двоичного дерева является максимальной глубиной этого двоичного дерева

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

1. Максимальная глубина бинарного дерева
   Максимальная глубина бинарного дерева может быть реализована с помощью рекурсивного метода, прохождения уровня и приоритета глубины, но самый простой и легкий — этоРекурсивный метод。

1. Рекурсивный метод

Рекурсивный методВысота корневого узла двоичного дерева является максимальной глубиной этого двоичного дереваЭта функция находит глубину двоичного дерева с высотой корневого узла.

1) Определить рекурсивные три элемента

1. Возвратное значение и параметры рекурсивной функции: возвращаемое значение — максимальная глубина текущего узла, а параметр — текущий узел
2. Логика отдельного слоя рекурсивной функции: максимальная глубина текущего узла = 1 + максимальная глубина левого ребенка или правого поддерево
3. Условие завершения рекурсивной функции: когда текущий узел пуст, максимальная глубина текущего узла составляет 0

2) Код рекурсивного метода (фактически, код поиска высоты корневого узла)

class Solution   public: // рекурсивные параметры и возвратные значения int maxDepth(TreeNode* root)   // Условия рекурсивного прекращения if(root == nullptr) return 0; // одиночная рекурсивная логика int leftdepth = maxDepth(root->left); int rightdepth = maxDepth(root->right); return 1 + max(leftdepth, rightdepth); > >; 

2. Как уровень

Идея иерархического обхода очень проста. Каждый слой пересекается, и MaxDepth + 1 разрешается возвращать максимальный

1) Как уровень кода

class Solution   public: int maxDepth(TreeNode* root)   queueTreeNode*> que; int maxdepth = 0; if(root == nullptr) return maxdepth; que.push(root); while(!que.empty())  int size = que.size(); // пересечение текущего слоя, глубина +1 maxdepth++; for(int i = 0; i  size; i++)  TreeNode* node = que.front(); que.pop(); if(node->left) que.push(node->left); if(node->right) que.push(node->right); > > return maxdepth; > >; 

3. Раннее предпочтительное обход

Самая глубокая глубина глубины обхода, зарегистрированной в процессе пересечения, — максимальная глубина.Этот метод не рекомендуетсяКод и логика не имеют четкого обхода и рекурсии.

1) В кодексе обхода приоритета приоритета

class Solution   public: int maxDepth(TreeNode* root)   stackTreeNode*> st; if (root != NULL) st.push(root); int depth = 0; int result = 0; while (!st.empty())   TreeNode* node = st.top(); if (node != NULL)   st.pop(); st.push(node); // середина st.push(NULL); // посетите первый слой, глубина +1 depth++; if (node->left) st.push(node->left); // Левый if (node->right) st.push(node->right); // верно > else   st.pop(); node = st.top(); st.pop(); Посетите первый слой, глубина -1 depth--; > // Записать самую глубокую глубину встречи во время процесса доступа result = result > depth ? result : depth; > return result; > >; 

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

1. Идея решения

Этот вопрос является максимальным продвижением бинарного дерева. Когда рекурсивно максимальная глубина большего

2. Код задачи -Код, разрешающий код,

class Solution   public: int maxDepth(Node* root)   // Условия рекурсивного прекращения if(root == nullptr) return 0; // рекурсивная логика одно -слойной линии: назад 1 + максимальная глубина поддерево int maxdepth = 0; // Обратите внимание, что для каждого узла вы должны получить количество деревьев его сынов for(int i = 0; i  root->children.size(); i++)  maxdepth = max(maxdepth, maxDepth(root->children[i])); > return 1 + maxdepth; > >; 

В -третьих, минимальная глубина бинарного дерева

1. Рекурсивный метод

1) Определить рекурсивные три элемента

1. Возвратное значение и параметры рекурсивной функции: возвращаемое значение — минимальная глубина текущего узла, а параметр — текущий узел
2. Единственная логика рекурсивной функции: минимальная глубина текущего узла = 1 + минимальная глубина левого подзадачи и правого поддерею
3. Условие завершения рекурсивной функции: когда текущий узел пуст, минимальная глубина текущего узла составляет 0

Однако в одной логике слоя мы должны обратить на это внимание,Когда есть только одно детское дерево, минимальная глубина двух подчин., Как показано на рисунке:

• Когда I -подэри узла x пуст, а дерево J Zish не пустое, минимальная глубина узла x = 1 + J Zishu’s Minimum Dybine

2) рекурсивный код

class Solution   public: // рекурсивное возвратное значение и параметры int minDepth(TreeNode* root)   // Условия рекурсивного прекращения if(root == nullptr) return 0; // рекурсивная единая логика int leftdepth = minDepth(root->left); int rightdepth = minDepth(root->right); // Обработка одного дерева пуста if(root->left && !root->right) return 1 +leftdepth; if(!root->left && root->right) return 1 + rightdepth; // Два суб -трищика не пустые return 1 + min(leftdepth, rightdepth); > >; 

2. Метод итерации

Бинарное дерево пересекается иерархией. Когда первое левое и правое подборе пусто

class Solution   public: int minDepth(TreeNode* root)   queueTreeNode*> que; int mindepth = 0; if(root == nullptr) return mindepth; que.push(root); while(!que.empty())  int size = que.size(); // Начнете пройти этот слой, запись глубины +1 mindepth++; for(int i = 0; i  size; i++)  TreeNode* node = que.front(); que.pop(); if(node->left) que.push(node->left); if(node->right) que.push(node->right); // Когда левый и правый подразделы пустые, вернуться if(!node->left && !node->right) return mindepth; > > return mindepth; > >; 

Источник