Сегодня мы рассмотрим следующую задачу, указанную как сложная, с степенью приемлемости 38,6% на момент написания.
Проблема выглядит следующим образом:
Учитывая
root
бинарного дерева, вычислите вертикальный обход бинарного дерева.
Для каждого узла в позиции
(row, col)
его левый и правый потомки будут в позициях(row + 1, col - 1)
и(row + 1, col + 1)
соответственно. Корень дерева находится в(0, 0)
.
Обход по вертикали бинарного дерева представляет собой список упорядочений сверху вниз для каждого индекса столбца, начиная с крайнего левого столбца и заканчивая самым правым столбцом. В одной строке и столбце может быть несколько узлов. В таком случае отсортируйте эти узлы по их значениям.
Возвращает вертикальный обход бинарного дерева.
Вот мое решение:
Прежде всего, я просматриваю все бинарное дерево один раз, собирая данные о координатах x и y и значениях. Для каждого узла я помещаю данные в coordArray
с помощью функции transNodes
.
Затем я помещаю этот массив в алгоритм сортировки, который сортирует по следующим критериям в заданном порядке:
- Если x и y двух массивов совпадают, отсортируйте по значению.
- В противном случае, если x совпадают, сортируйте по координатам y.
- В противном случае отсортируйте по координатам x.
С моими результатами я сформировал результирующий массив с именем res
, в котором первый элемент внутри него является значением первого узла в coordArray
.
Был выполнен последний цикл, начиная со второго элемента в пределах coordArray
, который проверяет, совпадают ли значения x каждого вложенного массива. Если они совпадают, значение вложенного массива будет помещено в последний вложенный массив res
. В противном случае новый вложенный массив будет помещен в res
со значением внутри.
И при этом возвращенный массив res
вернет решение проблемы. Решение имеет временную сложность O(n) и пространственную сложность O(n). Его время выполнения превышает 66,58% представлений, а использование памяти превышает 39,73% представлений.