Сегодня мы рассмотрим следующую задачу, указанную как сложная, с степенью приемлемости 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% представлений.