Вопрос

В этой статье мы рассмотрим 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) довольно просто. Выполните предварительный обход и отправьте узлы в новый список. Для этого вопроса мы собираемся изменить дерево на месте.

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

Сначала это может показаться сложным, но на самом деле это довольно просто. Пока вы понимаете концепции ниже.

Рекомендуемые знания

  1. Бинарное дерево
  2. Поиск в глубину
  3. Обход почтовых заказов
  4. Обход предзаказа
  5. Связанный список

Что мы знаем?

  1. У нас есть бинарное дерево (в большинстве случаев оно может быть пустым)
  2. Нам нужно свести дерево в связанный список.
  3. Нам нужно пройти дерево в обратном порядке, чтобы достичь этого за O(h) пространства
  4. Нам нужно переместить левое дерево в правое дерево текущего узла

Как мы собираемся это сделать:

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

  1. Используйте post_order_traversal, чтобы получить узлы в почтовом порядке
  2. Продолжайте обход узлов в обратном порядке, пока не найдем узел с left узлом.
  3. Как только мы обнаружим, что left node, мы собираемся инициализировать новый указатель с именем lefts_right_most_node. Его задача — найти root.left дальний правый узел. Мы собираемся использовать цикл while, чтобы продолжать получать right узлов, пока не найдем их. Причина, по которой мы это делаем, заключается в том, что самый дальний правый узел будет использоваться для соединения нижней части этого поддерева с current правым узлом. Мы делаем это, потому что мы собираемся объединить 2 поддерева в одно.
  4. Как только мы нашли lefts_right_most_node, мы собираемся соединить lefts_right_most_node с current правым узлом.
  5. Затем мы перезаписываем правый узел узла current узлом lefts_right_most_node. Это работает, потому что последний узел в левом дереве соединяется с текущим правым узлом. Таким образом, он вставляет все левое дерево в правое дерево, но перед всеми элементами правого дерева.
  6. Затем мы стираем узел left узла current. Это потому, что мы уже переместили левое дерево в правое, поэтому нам больше не нужно на него ссылаться.
  7. Мы постоянно делаем это, пока не достигнем конца обхода почтового заказа.

Обозначение большого 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;
};