814. Обрезка бинарного дерева 🚀


Решение разработано в:

Вопрос

В этой статье мы рассмотрим вопрос Leetcode ‘814. Обрезка двоичного дерева». Этот вопрос оценивается как средний.

Вопрос:

Задав корень двоичного дерева, верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.

Поддерево node — это узел плюс каждый узел, который является потомком node.

Пример:

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.
Вход в полноэкранный режим Выход из полноэкранного режима

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

Этот вопрос оценивается как средний. Хотя вопрос плохо сформулирован, ясно, что нам дано двоичное дерево и нам нужно удалить все поддеревья, не содержащие 1.

По сути, нас спрашивают: «Содержит ли это поддерево хоть одну 1?». Если да, оставьте его. Если нет, удалите его.

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

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

  1. Бинарное дерево
  2. Поиск по глубине
  3. Порядковый обход
  4. Рекурсия

Что мы знаем?

  1. У нас есть двоичное дерево
  2. Это двоичное дерево не содержит ничего, кроме 1 или 0.
  3. Нам нужно проверить, содержат ли все поддеревья 1 или 0. Это означает, что мы должны начать с нижней части дерева и двигаться вверх, чтобы избежать решения методом перебора.

Как мы это сделаем:

Мы будем использовать Post Order Traversal для обхода дерева, начиная с самого низа. Мы сделаем это потому, что хотим, чтобы каждое поддерево было проверено до того, как мы проверим родительский узел. Это означает, что когда мы проверяем родительский узел, он уже знает, содержит ли какой-либо из его дочерних узлов 1.

  1. Обратный обход порядка и начало с самого низа нашего дерева
  2. Спросите, является ли текущий узел пустым узлом или нет. Если да, то у него не может быть 1 в дочерних узлах. Поэтому мы сообщаем, что это поддерево нуждается в обрезке.
  3. Затем мы спросим, содержит ли левое или правое дерево какие-либо 1s. Если нет, мы обрезаем это дерево, обнуляя его.
  4. Затем мы спрашиваем, содержит ли какое-либо из дочерних деревьев 1 или нет. Это делается для того, чтобы мы могли выдать родительским узлам наши результаты, что где-то в поддереве единица существует. Это делается для того, чтобы предотвратить обрезку целых поддеревьев.
  5. Мы повторяем этот процесс до тех пор, пока не будут проверены все узлы.
  6. Возвращаем новое обрезанное дерево.

Нотация Big O:

  • Временная сложность: O(n)| Где n — количество узлов в нашем двоичном дереве | Так как мы собираемся обойти все узлы в дереве в худшем случае, когда в дереве одни «1».
  • Пространственная сложность: O(h)| Где h — высота двоичного дерева | Поскольку мы собираемся хранить высоту дерева в стеке вызовов из-за обхода в порядке следования.

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

Результаты Leetcode:

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

  • Время выполнения: 90 мс, быстрее, чем 26,96% представленных в сети JavaScript для Binary Tree Pruning.
  • Использование памяти: 42,1 МБ, меньше, чем 92,19% онлайн-представлений JavaScript для обрезки двоичного дерева.


Решение

 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val   = (val===undefined ? 0 : val)
 * this.left  = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var pruneTree = function (root) {

    /* -------------------------------------------------------------------------- */
    /*                          814. Binary Tree Pruning                          */
    /* -------------------------------------------------------------------------- */

    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
     */

    // So how are we going to do it?
    // > We're going to perform post-order traversal
    // > where we ask every node:
    // > - Does your left tree have a 1 anywhere?
    // > - Does your right tree have a 1 anywhere?
    // > - If it has no 1, we prune it.
    // > - If any of them have a one, we let the parent node know

    const post_order_prune = (node) => {

        // End of tree. So of course, this tree has no 1s
        if (!node) {
            return false;
        }

        // Do either the right or left nodes have 1s?
        let left_contains_a_one  = post_order_prune(node.left);
        let right_contains_a_one = post_order_prune(node.right);

        // Left tree hasn't got a 1
        if (!left_contains_a_one) {
            // Prune it
            node.left = null;
        }

        // Right tree does not have a 1
        if (!right_contains_a_one) {
            // Prune it
            node.right = null;
        }

        // So did any of our trees contain a 1?
        // Let the parent know about this.
        // We do this because, you could have a 1 all the way the bottom of the tree.
        // Which we need to bubble all the way back up to the parent.
        if (left_contains_a_one || right_contains_a_one) {
            return true;
        }

        // After pruning
        // Return this nodes value (Truthy or falsely)
        return node.val;
    };

    // Start the prune of children
    post_order_prune(root);

    // So we have pruned the children, does the root node
    // need to be removed?
    if (!root.right && !root.left && root.val === 0) {
        root = null;
    }

    // Return the root
    return root;
};

Войдите в полноэкранный режим Выход из полноэкранного режима

Оцените статью
Procodings.ru
Добавить комментарий