563. Наклон бинарного дерева 🚀

Вопрос

В этой статье мы рассмотрим 563 Leetcode. Наклон бинарного дерева».

Вопрос:

По заданному root бинарного дерева вернуть sum наклона каждого узла дерева. Наклон узла дерева – это абсолютная разница между sum всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если узел не имеет левого потомка, то сумма значений узла левого поддерева рассматривается как 0. Правило аналогично, если у узла нет правильного дочернего элемента.

Пример:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

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

Этот вопрос имеет рейтинг Легкий. Что я считаю совершенно неточным и вводящим в заблуждение.

Я считаю, что этот вопрос можно считать простым только в том случае, если вы понимаете концепции среднего уровня. Например, как суммировать бинарное дерево, как проходить бинарное дерево и как рекурсивно проходить бинарное дерево. Что такое Post Order Traversal и как мы можем использовать его для вычисления сумм дерева. Если вы разбираетесь в концепциях среднего уровня, то вы можете легко понять этот вопрос, но сам вопрос не для людей, которые не знают этих концепций.

Нас просят вычислить разницу между суммами левого и правого поддерева каждого узла. Что означает: в каждом узле, который мы посещаем, получаем сумму левых и правых деревьев. Выясните разницу между ними. Затем мы можем добавить эту разницу к общей сумме. Мы повторяем этот процесс для каждого узла во всем дереве.

Что мы знаем?

У нас есть бинарное дерево (в большинстве случаев оно может быть пустым)
Нам нужно вычислить наклон каждого узла в дереве.
Нам нужно посетить каждый узел в дереве.
Нам нужно будет использовать Post Order Traversal для вычисления наклона каждого узла.

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

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

Наклон рассчитывается:

tilt = abs(left_subtree_sum - right_subtree_sum)

Мы собираемся объявить tilt_counter, который будет использоваться для хранения общего наклона всех узлов в дереве. Много (+=) операций.
Мы собираемся выполнить Post Order Traversal
В каждом узле мы получаем left_sum и right_sum текущего узла. Что представляет собой сумму левого и правого поддеревьев. (Не волнуйтесь, если это не имеет смысла, это скоро будет объяснено.)
Затем мы вычисляем tilt текущего узла. Мы делаем это, вычисляя абсолютную разницу между left_sum и right_sum. Затем это значение добавляется к tilt_counter.
Затем мы возвращаем сумму текущего узла. Сумма текущего узла вычисляется как (left_sum + right_sum + сумма текущего узла).
После вычисления мы возвращаем это значение. Поскольку мы используем Post Order Traversal, мы можем вернуть сумму текущего узла его родительскому узлу в дереве. Вот как мы получаем суммы поддеревьев в точке 3.

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

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

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

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

Время выполнения: 79 мс, быстрее, чем 80,75% при отправке JavaScript в режиме онлайн для Binary Tree Tilt.
Использование памяти: 47 МБ, менее 85,45 % онлайн-заявок JavaScript для Binary Tree Tilt.

Решение

var findTilt = function (root) {
    /* -------------------------------------------------------------------------- */
    /*                            563. Binary Tree Tilt                           */
    /* -------------------------------------------------------------------------- */
    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
     */
    // Our tilt counter (Keeps track of the diff between the left and right subtrees)
    let tilt_counter = 0;
    // Recursive function to traverse the tree
    // In a post order fashion, get all the sums for all the subtrees
    // we then figure out the difference between the left and right subtrees
    // and add that to the tilt counter. 
    const post_order_traversal = (node) => {
        // If the node does not exist.
        // It has no value and therefore it's a 0.
        if (!node) {
            return 0;
        }
        // Post Order, get me their SUMS!!!
        let left_sum  = post_order_traversal(node.left);
        let right_sum = post_order_traversal(node.right);
        // Figure out the difference between the left and right subtrees
        // We use the absolute value of the difference to keep track of the tilt
        tilt_counter += Math.abs(left_sum - right_sum);
        // Return the value of the node and it's subtrees.
        return left_sum + right_sum + node.val;
    };
    post_order_traversal(root);
    return tilt_counter;
};