Это первое из серии решений вопросов для собеседований по алгоритмам программирования и структуре данных. Я начинаю эту серию, потому что,
- Эгоистично, один из лучших способов действительно понять что-то - научить этому.
- Большинство онлайн-ответов на подобные вопросы показывают решение, не показывая, как вы могли добраться до него, не видя проблему раньше. В этих сообщениях я постараюсь логически разобраться с проблемами, используя пошаговый подход, который можно применить к другим проблемам, с которыми вы можете столкнуться.
В этих сообщениях я буду указывать вопросы, которые вы должны задать себе. В идеале, прекратите читать и подумайте об ответе на вопрос, прежде чем идти дальше всякий раз, когда вы видите жирный «спросите себя».
В этом первом вопросе задача состоит в том, чтобы написать функцию, которая может определить, может ли данный массив целых чисел представлять порядок обхода предварительного заказа BST (двоичного дерева поиска). Верните true, если это так, иначе false.
boolean couldBePreOrderTraversal(int[] keys);
Напомним вкратце об основах BST и обходов деревьев.
Спросите себя: как работают двоичные деревья поиска?
- BST - это двоичное дерево, содержащее узлы с левым указателем, правым указателем и некоторым сортируемым ключом (в этом примере - целым числом).
- Для любого данного узла в двоичном дереве все узлы слева от него имеют меньшие ключи сортировки.
- Для любого заданного узла в двоичном дереве все узлы справа от него имеют ключи сортировки, которые равны или больше, чем у данного узла.
Спросите себя: как работает обход предварительного заказа?
Обход предварительного заказа - это обход дерева сначала в глубину, при котором вы посещаете узлы в следующем порядке: корень, влево, вправо.
void preOrderTraversal(Node n) {
if (n == null) {
return;
}
visit(n); // visit the root
preOrderTraversal(n.left); // visit left
preOrderTraversal(n.right); // visit right
}
Спросите себя: какой пример ввода должен вернуть истину?
В приведенном выше примере дерева обход предварительного заказа будет рекурсивным следующим образом.
* preOrderTraversal(8)
* left preOrderTraversal(5)
* left preOrderTraversal(3)
* left preOrderTraversal(null)
* right preOrderTraversal(null)
* right preOrderTraversal(6)
* left preOrderTraversal(null)
* right preOrderTraversal(null)
* right preOrderTraversal(10)
* left preOrderTraversal(9)
* left preOrderTraversal(null)
* right preOrderTraversal(null)
* right preOrderTraversal(15)
* left preOrderTraversal(null)
* right preOrderTraversal(19)
* left preOrderTraversal(null)
* right preOrderTraversal(null)
Если ключи сортировки записываются в массив во время обхода, результат будет: [8, 5, 3, 6, 10, 9, 15, 19].
Теперь у нас есть один пример ввода, в котором наша функция должна возвращать значение true,
couldBePreOrderTraversal ([8, 5, 3, 6, 10, 9, 15, 19]) - ›true
Спросите себя: какие примеры должны возвращать false?
Давайте подумаем о контрпримерах, когда наша функция должна возвращать false с использованием различных алгоритмов обхода дерева.
Дерево можно было обойти, используя обход по порядку (влево, корень, вправо),
couldBePreOrderTraversal ([3, 5, 6, 8, 9, 10, 15, 19]) - ›false
Мы видим, что обход по порядку дает нам отсортированный список в возрастающем порядке, но наша проблема не решена с помощью такого очевидного наблюдения.
По дереву можно было пройти, используя обход после заказа (влево, вправо, корень),
couldBePreOrderTraversal ([3, 6, 5, 9, 19, 15, 10, 8]) - ›false
Дерево можно было обойти с помощью поиска в ширину (уровень за уровнем),
couldBePreOrderTraversal ([8, 5, 10, 3, 6, 9, 15, 19]) - ›false
Теперь у нас есть огромное количество сложных на вид примеров, но нет быстрых интуитивных наблюдений за решением. В некоторых задачах проработка некоторых примеров среднего размера вручную может помочь вам увидеть закономерности. В этом случае перейдем к другой стратегии.
Спросите себя: есть ли простое решение с использованием грубой силы?
Давайте еще раз посмотрим на предварительный заказ обхода BST: [8, 5, 3, 6, 10, 9, 15, 19]
Мы видим, что порядок обхода предварительного заказа отражен в этом списке.
[корень] + [левое поддерево] + [правое поддерево]
[8] + [5, 3, 6] + [10, 9, 15, 19]
Этот шаблон рекурсивно повторяется в каждом из поддеревьев.
[корень] + [левое поддерево] + [правое поддерево]
[5] + [3] + [6]
[корень] + [левое поддерево] + [правое поддерево]
[10] + [9] + [15, 19]
Спросите себя: как узнать, где заканчивается левое поддерево и начинается правое поддерево?
Мы знаем из определения BST, что узлы на левой стороне будут меньше или равны корню, а узлы на правой стороне будут больше, чем корень. Корень правого поддерева будет первым найденным значением, превышающим корень.
Если мы обнаруживаем в правом поддереве какие-либо значения, меньшие, чем корень, мы знаем, что дерево либо не является BST, либо оно не было пройдено с обходом предварительного заказа.
Это приводит нас к рекурсивному алгоритму грубой силы.
- rootValue = первое значение в массиве.
- Итерируйте и установите rootOfRightSubtree = первый найденный индекс со значением, большим, чем rootValue.
- Итерируйте от rootOfRightSubtree до конца и убедитесь, что все найденные нами значения больше, чем root.
- Рекурсивно вызываем себя по тому, что мы определили как левое и правое поддеревья.
Это решение приводит к сложности выполнения O (N²).
Спросите себя: есть ли лучшее решение?
Есть умное решение O (N) с использованием стека.
Предположим, мы перебираем нашу последовательность и помещаем элементы в стек, пока они остаются в порядке убывания. [8, 5, 3, 6, 10, 9, 15, 19]
В тот момент, когда мы встречаем число 6, мы видим, что он больше, чем последний элемент, который мы помещаем в стек (3). В предварительном обходе BST это означает, что все значения меньше 3 уже должны были появиться в порядке обхода. Если с этого момента мы встретим какие-либо значения больше 3, мы можем вернуть false. Когда мы смотрим на следующий элемент в стеке, 5, мы видим то же самое.
Это приводит к алгоритму, который на самом деле довольно просто закодировать, но сложно интуитивно придумать.
Что работает с временной сложностью O (N).
