Вопрос
В этой статье мы рассмотрим 114. Свести двоичное дерево к связанному списку.
Вопрос:
Учитывая
root
двоичного дерева, сведите дерево в "связный список": "связанный список" должен использовать тот же классTreeNode
, где дочерний указательright
указывает на следующий узел в списке, а дочерний указательleft
всегда равно нулю. «Связанный список» должен быть в том же порядке, что и обход в прямом порядке двоичного дерева.
Пример:
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Объяснение вопроса
Рейтинг этого вопроса средний. Что я считаю точным. Разобраться с этим вопросом в пространстве O(n) довольно просто. Выполните предварительный обход и отправьте узлы в новый список. Для этого вопроса мы собираемся изменить дерево на месте.
Нас просят превратить двоичное дерево в связанный список и сделать так, чтобы связанный список выглядел как двоичное дерево, проходимое в предварительном порядке.
Сначала это может показаться сложным, но на самом деле это довольно просто. Пока вы понимаете концепции ниже.
Рекомендуемые знания
Что мы знаем?
- У нас есть бинарное дерево (в большинстве случаев оно может быть пустым)
- Нам нужно свести дерево в связанный список.
- Нам нужно пройти дерево в обратном порядке, чтобы достичь этого за O(h) пространства
- Нам нужно переместить левое дерево в правое дерево текущего узла
Как мы собираемся это сделать:
Мы собираемся выполнить обход почтового заказа. Потому что мы хотим переместить все левое дерево текущего node
в правое дерево текущего node
. С концом этого левого дерева, указывающим на текущий узел right
. Это звучит запутанно, но не волнуйтесь, в этом есть смысл.
- Используйте
post_order_traversal
, чтобы получить узлы в почтовом порядке - Продолжайте обход узлов в обратном порядке, пока не найдем узел с
left
узлом. - Как только мы обнаружим, что
left node
, мы собираемся инициализировать новый указатель с именемlefts_right_most_node
. Его задача — найтиroot.left
дальний правый узел. Мы собираемся использовать циклwhile
, чтобы продолжать получатьright
узлов, пока не найдем их. Причина, по которой мы это делаем, заключается в том, что самый дальний правый узел будет использоваться для соединения нижней части этого поддерева сcurrent
правым узлом. Мы делаем это, потому что мы собираемся объединить 2 поддерева в одно. - Как только мы нашли
lefts_right_most_node
, мы собираемся соединитьlefts_right_most_node
сcurrent
правым узлом. - Затем мы перезаписываем правый узел узла
current
узломlefts_right_most_node
. Это работает, потому что последний узел в левом дереве соединяется с текущим правым узлом. Таким образом, он вставляет все левое дерево в правое дерево, но перед всеми элементами правого дерева. - Затем мы стираем узел
left
узлаcurrent
. Это потому, что мы уже переместили левое дерево в правое, поэтому нам больше не нужно на него ссылаться. - Мы постоянно делаем это, пока не достигнем конца обхода почтового заказа.
Обозначение большого O:
- Временная сложность: O(n) | Где n — количество узлов в нашем бинарном дереве | Поскольку мы собираемся пройти по всем узлам дерева.
- Сложность пространства: O(h) | Где h — высота узлов в нашем стеке вызовов | Поскольку мы используем стек рекурсивных вызовов для обхода дерева.
"Можно ли это улучшить?" Да! Morris Traversal может решить эту задачу в пространственной сложности O(1). Но Morris Traversal сложно и тяжело читать. Для простоты я его здесь не использую.
Результаты литкода:
Смотрите ссылку на отправку:
- Время выполнения: 56 мс, быстрее, чем 99,88 % онлайн-отправок JavaScript для Flatten Binary Tree to Linked List
- Использование памяти: 44,1 МБ, менее 90,67% онлайн-отправлений JavaScript для Flatten Binary Tree to Linked List
Решение
var flatten = function (root) {
// So, we're not going to traverse the tree in pre-order traversal. // Instead, we're going to do the opposite of what we was just asked to do. // The reason for this is we're optimising for space complexity. If we did pre-order // traversal, we would have to store an entirely new tree in memory. While in this solution, we only store // the height of the tree in memory.
// Do Post Order Traversal
// Base case, empty node if (!root) { return null; }
flatten(root.left); flatten(root.right);
// Now, we're at the left most node, // We're going to ask if this current node // even has a left node? // If it does, move it's entire left sub tree // into the right tree but in-order. :D
// Move the left tree to the right tree if (root.left) { // So, we're going to get the current left nodes // right most node. Because we're going to set this nodes // pointer to be the right node of the current node. let lefts_right_most_node = root.left;
// Get me the left's right most node while (lefts_right_most_node.right) { lefts_right_most_node = lefts_right_most_node.right; }
// Adjust the right most nodes pointer // to point to the current nodes right node lefts_right_most_node.right = root.right;
// Add the left tree into the right tree. root.right = root.left;
// Remove the left tree. We don't need it anymore. root.left = null; }
return root; };