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

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

Он возвращает превышение лимита времени. Интересно, знаю, почему это происходит, что не так с моим кодом?

Используя основную теорему и предполагая, что дерево сбалансировано, время работы составляет Omega(n^1.58) , но вы можете достичь O(n) (если я не пропустил какую-то другую ошибку)

2 ответа

Вы действительно близки. Я думаю, вы стремились к этому:

int maxHeight(TreeNode p) < if (p == null) return 0; int leftHeight = maxHeight(p.left); int rightHeight = maxHeight(p.right); return (leftHeight >rightHeight) ? leftHeight + 1 : rightHeight + 1; > 

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

Большое спасибо! Теперь я знаю, что использовал рекурсию больше раз. Я должен использовать его дважды каждый раз!

Трудно представить, что у вас возникнут проблемы с большинством бинарных деревьев, если только:

• это очень большое (и/или вырожденное) бинарное дерево; или
• он неправильно структурирован (например, в структуре есть круговая петля); или
• ваш лимит времени очень мал.

Так что это были бы первые вещи, которые я бы проверил.

Однако в вашем случае это, возможно, потому, что вы вызываете функцию рекурсивно гораздо чаще, чем вам нужно.

Имея в своем коде два вызова функции depth для каждого поддерева (один для сравнения глубины и один для возврата самого глубокого поддерева), вы значительно увеличиваете рабочую нагрузку. Было бы лучше кэшировать длины, чтобы вы могли их повторно использовать, что-то вроде (псевдокод):

def maxDepth(nd): if nd == null: # Empty-sub-tree depth is zero. return 0 deepest = maxdepth(nd.left) # Initially assume left is deepest. dright = maxdepth(nd.right) # Or use right if deeper. if dright > deepest: deepest = dright return 1 + deepest # Depth: this node plus deepest sub-tree. 

@wadda_wadda, это не совпадение. Если вы держитесь подальше от более эзотерических частей Python, это идеальный язык для обучения и псевдокодирования. Прелесть в том, что вы часто можете тестировать свой псевдокод и на реальной системе 🙂

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

Источник

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

Возвращает ограничение по времени. Интересно, знаю, почему это происходит, что не так с моим кодом?

2 ответа

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

int maxHeight(TreeNode p) < if (p == null) return 0; int leftHeight = maxHeight(p.left); int rightHeight = maxHeight(p.right); return (leftHeight >rightHeight) ? leftHeight + 1 : rightHeight + 1; > 

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

Трудно представить, что вы столкнетесь с проблемой большинства бинарных деревьев, если только:

• это действительно большое (и / или вырожденное) двоичное дерево; или же
• он не структурирован правильно (например, имеет круговую петлю в структуре); или же
• ваш лимит времени очень маленький.

Так что это будет первое, что я проверю.

Однако в вашем случае это возможно потому, что вы вызываете функцию рекурсивно гораздо чаще, чем вам нужно.

Имея два вызова функции глубины в вашем коде для каждого поддерева (один для сравнения глубин и один для возврата самого глубокого поддерева), вы значительно увеличиваете рабочую нагрузку. Было бы лучше кэшировать длины, чтобы вы могли их повторно использовать, что-то вроде (псевдокод):

def maxDepth(nd): if nd == null: # Empty-sub-tree depth is zero. return 0 deepest = maxdepth(nd.left) # Initially assume left is deepest. dright = maxdepth(nd.right) # Or use right if deeper. if dright > deepest: deepest = dright return 1 + deepest # Depth: this node plus deepest sub-tree. 

Источник

Как определить, сбалансировано ли двоичное дерево в Java

Узнайте, как определить, сбалансировано ли двоичное дерево в Java.

1. Обзор

Деревья являются одной из наиболее важных структур данных в области компьютерных наук. Обычно нас интересует сбалансированное дерево из-за его ценных свойств . Их структура позволяет выполнять такие операции, как запросы, вставки, удаления в логаритмическое время.

2. Определения

Во-первых, давайте введем несколько определений, чтобы убедиться, что мы находимся на той же странице:

• Двоичное дерево – своего рода дерево, где каждый узел имеет ноль, один или два ребенка
• Высота дерева – максимальное расстояние от корня до листа (так же, как глубина самого глубокого листа)
• Сбалансированное дерево – это своего рода дерево, на котором для каждого подтрибного максимальное расстояние от корня до любого листа не более чем на один больше, чем минимальное расстояние от корня до любого листа

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

3. Объекты домена

Итак, давайте начнем с класса для нашего дерева:

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

Прежде чем мы введем наш основной метод давайте посмотрим, что он должен вернуться:

Таким образом, для каждого вызова, мы будем иметь информацию о высоте и балансе.

4. Алгоритм

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

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

Теперь давайте посмотрим на наш метод глубины-первых:

private Result isBalancedRecursive(Tree tree, int depth) < if (tree == null) < return new Result(true, -1); >Result leftSubtreeResult = isBalancedRecursive(tree.left(), depth + 1); Result rightSubtreeResult = isBalancedRecursive(tree.right(), depth + 1); boolean isBalanced = Math.abs(leftSubtreeResult.height — rightSubtreeResult.height)

Во-первых, мы должны рассмотреть дело, если наш узел нулевой : Мы вернемся истинное (что означает, что дерево сбалансировано) и -1 в высоту.

Затем, мы делаем два рекурсивных звонка для левого и правого подтри, сохраняя глубину в курсе .

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

• isBalanced переменная проверяет высоту для детей, и
• substreesAreBalanced указывает, если подтрири оба сбалансированы, а также

Наконец, мы можем вернуть информацию о балансе и высоте. Это также может быть хорошей идеей, чтобы упростить первый рекурсивный вызов с методом фасада:

public boolean isBalanced(Tree tree)

5. Резюме

В этой статье мы обсудили, как определить, сбалансировано ли двоичное дерево. Мы объяснили подход к поиску в первую очередь.

Как обычно, исходный код с тестами доступен более на GitHub .

Читайте ещё по теме:

Источник

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

Проблема алгоритма LeetCode — максимальная глубина N-арного дерева (реализация на Java)

Это часть книги Юэле261Обновление, сначала274оригинал

01 Чтение вопросов и подготовка

Сегодня я представлю 128-й вопрос уровня Easy в вопросе алгоритма LeetCode (номер вопроса — 559). Для n-арного дерева найдите его максимальную глубину. Максимальная глубина — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла. Например, для 3-х арочного дерева:

Мы должны вернуть его максимальную глубину, равную 3.

Средством разработки, используемым для решения этой проблемы, является eclipse, jdk использует версию 1.8, среда — 64-битная система win7, а для написания и тестирования используется язык Java.

02 Первое решение

Этот вопрос аналогичен поиску максимальной глубины двоичного дерева, за исключением того, что двоичное дерево имеет только левый и правый дочерние узлы, а дочерние узлы этого n-арного дерева представляют собой массив, содержащий несколько узлов, поэтому нам нужно заменить только левый и правый дочерние узлы. , Он становится циклом for для обработки.Узлы, содержащиеся в массиве, на самом деле являются подзадачей проблемы, поэтому мы используем рекурсию, вызываем сам метод и, наконец, возвращаем максимальное значение.

/* // Definition for a Node. class Node < public int val; public Listchildren; public Node() <> public Node(int _val,List _children) < val = _val; children = _children; >>; */ class Solution < public int maxDepth(Node root) < if (root == null) < return 0; >if (root.children == null) < return 1; >int max = 0; for (Node node : root.children) < max = Math.max(max, maxDepth(node)); >return max+1; > > 

03 Второе решение

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

/* // Definition for a Node. class Node < public int val; public Listchildren; public Node() <> public Node(int _val,List _children) < val = _val; children = _children; >>; */ class Solution < public int maxDepth(Node root) < if (root == null) < return 0; >if (root.children == null) < return 1; >Queue queue = new LinkedList(); queue.offer(root); int depth = 0; while (!queue.isEmpty()) < int size = queue.size(); for (int i=0; i> depth++; > return depth; > > 

04 Резюме

Тема алгоритма былаБолее трех месяцев в день, Статья с вопросом об алгоритмах128+ Статья, ответ на официальный диалог аккаунта 【Структуры данных и алгоритмы】、【алгоритм】、【структура данныхЛюбое ключевое слово в】, получите серию статей.

Выше приведен весь контент. Если у вас есть какие-либо хорошие идеи, предложения или другие вопросы, вы можете оставить сообщение ниже, чтобы обменяться, например, оставить сообщение, и пересылка — это лучший ответ и поддержка для меня!

Источник