JavaScript | инвертировать дерево | Зеркальное дерево | Структура данных

Перевернутая форма двоичного дерева — это еще одно двоичное дерево, в котором левые и правые дочерние элементы всех нелистовых узлов поменяны местами. Вы также можете назвать его зеркалом входного дерева.

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

Рекурсивное решение

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

• Когда дерево пусто, верните NULL. Это также наш базовый вариант для остановки рекурсивных вызовов.
• Для каждого обнаруженного узла мы меняем местами его левый и правый дочерние элементы, прежде чем рекурсивно инвертировать его левое и правое поддерево.

var invertTree = function(root) {
    if(!root) return root;
    
   function traverse(node) {
        if(!node) return null;
        const newNode = { val: node.val };
        newNode.left = traverse(node.left);
        newNode.right = traverse(node.right);
        
        //swap
        let temp = newNode.left;
        newNode.left = newNode.right;
        newNode.right = temp;
        return newNode;
    }
    
    return traverse(root);
};

Анализ сложности

В приведенном выше подходе мы проходим каждый узел дерева только один раз. Временная сложность: O(n)

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