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

Вопрос

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

Вопрос:

Задав корень двоичного дерева, верните сумму наклона каждого узла дерева.
Наклон узла дерева — это абсолютная разность между 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 и как мы можем использовать его для вычисления сумм деревьев. Если вы понимаете концепции среднего уровня, то вы сможете легко понять этот вопрос, но сам вопрос не для тех, кто не знает этих концепций.

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

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

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

Что мы знаем?

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

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

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

Наклон вычисляется следующим образом:

tilt = abs(left_subtree_sum - right_subtree_sum)

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

Нотация Big O:

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

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

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

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

• Время выполнения: 79 мс, быстрее, чем 80,75% представленных в сети JavaScript для наклона двоичного дерева.
• Использование памяти: 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;
};