Задача: 987. Vertical Order Traversal of a Binary Tree
Сложность: medium

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

👨‍💻 Алгоритм:

1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).

2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).

3⃣Возврат результата:
Отсортировать ключи словаря по col и затем по row.
Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список.

😎 Решение:

var verticalTraversal = function(root) {
    const colTable = new Map();
    const queue = [[root, 0, 0]];

    while (queue.length > 0) {
        const [node, row, col] = queue.shift();
        if (node) {
            if (!colTable.has(col)) {
                colTable.set(col, []);
            }
            colTable.get(col).push([row, node.val]);
            queue.push([node.left, row + 1, col - 1]);
            queue.push([node.right, row + 1, col + 1]);
        }
    }

    const sortedCols = Array.from(colTable.keys()).sort((a, b) => a - b);
    const result = [];

    for (const col of sortedCols) {
        colTable.get(col).sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
        result.push(colTable.get(col).map(pair => pair[1]));
    }

    return result;
};

Ставь 👍 и забирай 📚 Базу знаний