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

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

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

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

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

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

Источник

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

Минимальная глубина 13 двоичного дерева (Leecode 111)

1 проблема

Учитывая двоичное дерево, чтобы найти его минимальную глубину.

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

ПРИМЕЧАНИЕ. Узлы листьев относятся к узлам без подпрограмм.

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

Вернемся к минимальной глубине 2.

2 решения

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

Название: «Минимальная глубина — это количество узлов на кратчайшем пути от корневого узла до недавних листовых узлов.» Обратите внимание, что это «листовой узел».
Что такое листовой узел, узлы левого и правого детей — это листья узлы!
Следовательно, если дерево левого дерева пустое, а правая поддерево не является пустым, это означает, что минимальная глубина — глубина 1 + правого поддерево.
И наоборот, правое дерево дерева пустое, левое детское дерево не пустое, а минимальная глубина — глубина 1 + левого поддерева. В конце концов, если левые и правые деревья не являются пустыми, значение глубины левого и правого поддерека составляет + 1.

/** * Definition for a binary tree node. * struct TreeNode < * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) <>* TreeNode(int x) : val(x), left(nullptr), right(nullptr) <> * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) <> * >; */ class Solution   public: int getDepth(TreeNode* node)   if(node == nullptr) return 0; int leftDepth = getDepth(node->left); int rightDepth = getDepth(node->right); // Если дерево левого дерева пустое, глубина дерева - глубина правого дерева +1 if(node->left == nullptr && node->right != nullptr) return 1 + rightDepth; // Если правое дерево пустое, глубина дерева -глубина левого подэреа +1 if(node->right == nullptr && node->left != nullptr) return 1 + leftDepth; return 1 + min(leftDepth, rightDepth); > int minDepth(TreeNode* root)   return getDepth(root); > >; 

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

2.2 Метод итерации

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

class Solution   public: int minDepth(TreeNode* root)   if (root == NULL) return 0; int depth = 0; queueTreeNode*> que; que.push(root); while(!que.empty())   int size = que.size(); depth++; // Записать минимальную глубину int flag = 0; 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)   // Когда дети пусты, это означает, что это слой самой низкой точки, выход flag = 1; break; > > if (flag == 1) break; > return depth; > >; 

Источник

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

Пример: дано двоичное дерево [3,9,20, null, null, 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)  if(root == NULL) return 0; else return 1 + min(minDepth(root->left),minDepth(root->right)); > >; 

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

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

 int minDepth(TreeNode* root)  if(root == NULL) return 0; int l = minDepth(root->left); int r = minDepth(root->right); if(root->left == NULL || root->right == NULL) // Определяем, является ли это листовым узлом return l == 0 ? ++r : ++l; return 1 + min(l,r); > 

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

 int minDepth(TreeNode* root)  queueTreeNode*> tr; int times = 0; if (root == nullptr) return 0; tr.push(root); times = 1; while (!tr.empty())  TreeNode* cur = tr.front(); tr.pop(); if (cur->left == nullptr && cur->right == nullptr) return times; else  if (cur->left != nullptr) tr.push(cur->left); if (cur->right != nullptr) tr.push(cur->right); ++times; > > > 

Источник

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

LeetCode111-C ++ многоуровневое подробное объяснение минимальной глубины двоичного дерева

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

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

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

Пример:

Дано бинарное дерево [3,9,20,null,null,15,7] ,

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

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

// Этот метод не имеет тайм-аута на OJ int maxDepth(TreeNode *p) < if(!p) return 0; int lengthl = maxDepth(p->left)+1; int lengthr = maxDepth(p->right)+1; return lengthl>lengthr?lengthl:lengthr; > // Написана следующая, казалось бы, непобедимая и краткая логика, и OJ будет GG int maxDepth(TreeNode *p) < if(!p) return 0; return maxDepth(p->left)>maxDepth(p->right)?:maxDepth(p->left)+1:maxDepth(p->right)+1; > 

Для товарищей с немного меньшим количеством кода, если вы спросите всех, какой метод лучше, вы должны без стеснения сказать следующее: кажется, что он действительно немного выше, а объем кода короче. Но все игнорируют проблему: в выражении возврата следующего метода одна и та же формула фактически рекурсивно параллельна дважды. Тогда причина этого времени ожидания записи напрямую связана со временем * 2. На более глубоком уровне, если указатель изменяется в теле функции, этот метод вызовет ошибку, то есть параметры в одном и том же выражении до и после двух точек не совпадают.

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

return lengthl>lengthr?lengthr:lengthl;

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

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

class Solution < public: int minDepth(TreeNode* root) < if(!root) return 0; if(!root->left&&!root->right) return 1; else if((!root->left&&root->right)||(root->left&&!root->right)) < root = root->left?root->left:root->right; return minDepth(root)+1; > int lengthl = minDepth(root->left)+1; int lengthr = minDepth(root->right)+1; return lengthl>lengthr?lengthr:lengthl; > >;

Когда мы сталкиваемся с узлом со степенью 1, мы искусственно позволяем ему продолжить движение по непустому потомку ~

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

 class Solution < private: queuea; public: int minDepth(TreeNode* root) < if(!root) return 0; int count = 1; a.push(root); while(!a.empty()) < int size = a.size(); for(int i = 0;iright) < a.push(b->right); > if(b->left) < a.push(b->left); > if(!b->right&&!b->left) < return count; >> count++; > return count; > >;

Здесь есть небольшая яма. Во время цикла for каждый должен обращать внимание на то, чтобы не использовать a.size () в качестве верхней границы. Причина очень проста: каждый раз, когда pop () или Push (), a.size () изменяется, то есть, если size () используется в качестве верхней границы, то верхняя граница каждого для выполнения цикла постоянно плавает. , То есть верхние границы, соответствующие i и i + 1, различны.

2333, немного потерял дар речи, но Сяо Ханг должен обратить внимание

Источник

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

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

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

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

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

Пример:
Учитывая двоичное дерево [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 ++

Источник