Сжать бинарное дерево сверху вниз с условием перекрытия

Опубликовано: 22 Сентября, 2022

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

Примеры:

Input: 
 

     1
      
       2
      /
     1
      
       3

Output: 1 2 
Explanation: 
1 and 1 are at same vertical distance, count of set bit at 0th position = 2 and count of clear bit = 0. Therefore, 0th bit of the resultant node is set. 
2 and 3 are at same vertical distance, count of set bit at 0th pos = 1 and count of clear bit = 1. Therefore, 0 bit is set of resultant node is not set. 
2 and 3 are at same vertical distance, count of set bit at 1st pos = 2 and count of clear bit = 0. Therefore, 1st bit of resultant node is set. 
 

 

Input: 
 

       1
     /   
    3     2
   /    /  
  1   4 1    2

Output: 1 3 5 2 2 
 

 

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

  • Карта может использоваться для хранения горизонтального расстояния от корневого узла в качестве ключа и значений узлов в качестве значений .
  • После сохранения значений на карте проверьте количество установленных и неустановленных битов для каждой позиции и соответствующим образом рассчитайте значения.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ