Задача: 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 обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам.

😎 Решение:

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<IList<int>> VerticalOrder(TreeNode root) {
        IList<IList<int>> output = new List<IList<int>>();
        if (root == null) {
            return output;
        }

        Dictionary<int, List<int>> columnTable = new Dictionary<int, List<int>>();
        Queue<(TreeNode, int)> queue = new Queue<(TreeNode, int)>();
        int column = 0;
        queue.Enqueue((root, column));

        while (queue.Count > 0) {
            var (node, col) = queue.Dequeue();

            if (node != null) {
                if (!columnTable.ContainsKey(col)) {
                    columnTable[col] = new List<int>();
                }
                columnTable[col].Add(node.val);

                queue.Enqueue((node.left, col - 1));
                queue.Enqueue((node.right, col + 1));
            }
        }

        var sortedKeys = new List<int>(columnTable.Keys);
        sortedKeys.Sort();
        foreach (var key in sortedKeys) {
            output.Add(columnTable[key]);
        }

        return output;
    }
}

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