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

Дан корень бинарного дерева, верните вертикальный порядок обхода значений его узлов (т.е. сверху вниз, столбец за столбцом).
Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.

Пример:

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

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

1⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.

2⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

3⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам.

😎 Решение:

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class Solution {
    verticalOrder(root) {
        const output = [];
        if (root === null) {
            return output;
        }

        const columnTable = new Map();
        const queue = [];
        let column = 0;
        queue.push([root, column]);

        while (queue.length > 0) {
            const [node, col] = queue.shift();

            if (node !== null) {
                if (!columnTable.has(col)) {
                    columnTable.set(col, []);
                }
                columnTable.get(col).push(node.val);

                queue.push([node.left, col - 1]);
                queue.push([node.right, col + 1]);
            }
        }

        const sortedKeys = Array.from(columnTable.keys()).sort((a, b) => a - b);
        for (const key of sortedKeys) {
            output.push(columnTable.get(key));
        }

        return output;
    }
}

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