Вопрос

В этой статье мы рассмотрим Leetcode 226. Инвертировать бинарное дерево. Этот вопрос оценивается как простой вопрос.

Вопрос:

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

Пример:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Объяснение вопроса

Нам нужно инвертировать бинарное дерево. Как будто вы поднесли зеркало к дереву. Это означает, что на каждом node мы должны поменять местами узлы left и right. Мы продолжаем это до тех пор, пока у нас не останется больше узлов.

Итак, начиная с нижней части дерева, мы поменяем местами узел left с узлом right и наоборот.

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

  1. Бинарные деревья
  2. Путешествие по почте
  3. Деструктуризация массива. (ES6) (необязательно)

Что мы знаем?

  1. У нас есть дерево, и мы должны инвертировать его. Другими словами, left узлов становятся right узлами, а right узлов становятся left узлами.

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

Мы собираемся использовать Post Order Traversal, чтобы инвертировать tree. Это означает, что мы начнем с самого нижнего левого края дерева и вернемся к root дерева.

Затем мы собираемся поменять местами узлы left и right. Мы проделаем это с каждым узлом в дереве, пока не вернемся к root узлу.

  1. Поскольку мы идем рекурсивно, все, что мы собираемся сделать, это поменять местами левый и правый узлы на каждом узле, к которому мы идем.
  2. Во-первых, мы делаем это, проверяя, что узел вообще существует. Это для крайних случаев и когда мы достигаем конца дерева.
  3. Мы объявляем временную переменную для хранения левого узла (поскольку мы собираемся переопределить ее, но она нам понадобится позже).
  4. Затем мы меняем местами левый и правый узлы. С помощью этой временной переменной.
  5. Затем мы делаем это для всех левых узлов данного дерева, а затем для всех правых узлов данного дерева. Порядок этой части не имеет значения, если вы поменяете их местами.
  6. Предполагая, что мы поменяли местами левый и правый узлы, мы возвращаем корневой узел. Мы делаем это, потому что собираемся вызывать эту функцию рекурсивно. Итак, мы можем вернуться в стек. Но это в основном важно, когда мы достигли последнего узла в стеке.

Обозначение большого O:

  • Временная сложность: O(n) | Где n — это количество узлов дерева | Потому что мы проходим по каждому узлу.
  • Сложность пространства: O(h) | Где h – это максимальная высота дерева | Потому что это будет размер стека вызовов | Хотя можно утверждать, что это O (n), поскольку в худшем случае стек вызовов может быть таким же глубоким, как ВСЁ дерево.

‘ Можно ли это улучшить? ‘ Да! Morris Traversal может решить эту задачу в пространственной сложности O(1). Но Morris Traversal сложно и тяжело читать. Для простоты я его здесь не использую.

Результаты литкода:

Смотрите ссылку на отправку:

  • Время выполнения: 61 мс, что быстрее, чем 87,47% при отправке JavaScript в Интернете для Invert Binary Tree.
  • Использование памяти: 47 МБ, менее 40,24 % онлайн-заявок JavaScript для Invert Binary Tree.

Решение 1

var invertTree = function (root) {
    /* -------------------------------------------------------------------------- */
    /*                           226. Invert Binary Tree                          */
    /* -------------------------------------------------------------------------- */
    // We have reached a leaf node, so we need to bubble back up the stack.
    // To the next node.
    if (!root) {
        return root;
    }
    // A temporary variable to hold the left node (As we're about to override it but still need it for later).
    let temp_node = root.left;
    // We then swap the left and right nodes. With the help of that temporary variable.
    root.left  = root.right;
    root.right = temp_node;
    // We then do this for all the left nodes of the given tree, and then all the right nodes of a given tree.
    invertTree(root.left);
    invertTree(root.right);
    // Assuming we have swapped our left and right nodes, we return the root node.
    return root;
};

Решение 2

var invertTree = function (root) {
    // We have reached a leaf node, so we need to bubble back up the stack.
    // To the next node.
    if (!root) {
        return root;
    }
    // ES6 Destructuring.
    // What this does is take the left and right nodes and swap them.
    // But without the need of a temp variable. As in object destructuring, it remembers.
    // Although, if you're a performance fanatic, this isn't efficient. 
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
    return root
};