Сложность: 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 и значениям, и добавить их в результирующий список.
😎 Решение:
class Solution {
func verticalTraversal(_ root: TreeNode?) -> [[Int]] {
var colTable = [Int: [(Int, Int)]]()
var queue: [(TreeNode?, Int, Int)] = [(root, 0, 0)]
while !queue.isEmpty {
let (node, row, col) = queue.removeFirst()
if let node = node {
if colTable[col] != nil {
colTable[col]!.append((row, node.val))
} else {
colTable[col] = [(row, node.val)]
}
queue.append((node.left, row + 1, col - 1))
queue.append((node.right, row + 1, col + 1))
}
}
var result = [[Int]]()
for key in colTable.keys.sorted() {
colTable[key]!.sort { $0 < $1 }
result.append(colTable[key]!.map { $0.1 })
}
return result
}
}Ставь 👍 и забирай 📚 Базу знаний