Создайте массив, представляющий GCD узлов каждого вертикального уровня двоичного дерева.

Для заданного бинарного дерева задача состоит в том, чтобы построить массив так, чтобы i ^-й индекс массива содержал НОД всех узлов, присутствующих на i ^-м вертикальном уровне данного бинарного дерева.

Примеры:

Input: Below is the given Tree:
                                                 5
                                                /  
                                            4       7 
                                         /          
                                      8    10       6
                                       
                                        8

Output: {8, 4, 5, 7, 6}

Explanation:
Vertical level I -> GCD(8) = 8.
Vertical level II -> GCD(4, 8) = 4.
Vertical level II -> GCD(5, 10) = 5.
Vertical level IV -> GCD(7) = 7.
Verticleal level V -> GCD(6) = 6

Input: Below is the given Tree:
                                                 4
                                               /    
                                            2       3
                                         /      /     
                                      3     2 4     5      

Output: {3, 2, 2, 3, 5}

Подход: Данную проблему можно решить, выполнив обход заданного дерева в вертикальном порядке и сохранив значение каждого узла, которое встречается в тех же вертикальных линиях, а затем распечатайте НОД всех значений, сохраненных для каждого уровня. Выполните следующие шаги, чтобы решить эту проблему:

• Инициализируйте карту M для хранения GCD всех узлов для каждой вертикальной линии при выполнении обхода.
• Инициализируйте переменную, скажем, hd как 0 , чтобы отслеживать горизонтальное расстояние.
• Рекурсивно пройдите по данному дереву и выполните следующие шаги:
  • Сохраните значения текущего узла на карте M как ключ как hd и значение как значение узла .
  • Уменьшите переменную hd на 1 и рекурсивно вызовите левое поддерево.
  • Увеличьте переменную hd на 1 и рекурсивно вызовите правое поддерево.
• Пройдите карту и найдите НОД всех узлов, хранящихся на карте, для каждого горизонтального расстояния в качестве ключа и распечатайте полученное значение НОД.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)