Вывести все возможные N-узлы Полные бинарные деревья

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

Учитывая целое число N , задача состоит в том, чтобы напечатать все возможные полные двоичные деревья с N узлами. Значение в узлах не способствует тому, чтобы быть критерием для другого полного двоичного дерева, за исключением NULL, поэтому примите их как 0.

Полное бинарное дерево — это бинарное дерево, в котором каждый узел имеет ровно 0 или 2 дочерних элемента.

Примеры:

Input:  N = 7
Output: [[0, 0, 0, null, null, 0, 0, null, null, 0, 0, null, null, null, null],
              [0, 0, 0, null, null, 0, 0, 0, 0, null, null, null, null, null, null],
             [0, 0, 0, 0, 0, null, null, null, null, 0, 0, null, null, null, null],
             [0, 0, 0, 0, 0, null, null, 0, 0, null, null, null, null, null, null],
            [0, 0, 0, 0, 0, 0, 0, null, null, null, null, null, null, null, null]]
Explanation: The possible full binary trees are – 
    0           |          0            |           0             |        0                |                   0
   /          |         /           |         /             |       /               |                  /  
 0   0         |       0   0          |       0   0           |      0   0              |               0   0
     /        |          /          |     /                |     /                  |              / /
   0   0       |        0   0         |   0   0               |   0   0                 |            0  0 0  0
       /      |       /             |       /              |  /                     |
     0   0     |    0   0             |     0   0             | 0   0                   |

 Input: N = 5
Output: [[0, 0, 0, null, null, 0, 0, null, null, null, null],
[0, 0, 0, 0, 0, null, null, null, null, null, null]]

Input: N = 9

Output: [[0,0,0,null,null,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,null,null,0,0,0,0],[0,0,0,null,null,0,0,0,0,0,0],[0,0,0,null,null,0,0,0,0,null,null,null,null,0,0],[0,0,0,null,null,0,0,0,0,null,null,0,0],[0,0,0,0,0,0,0,null,null,null,null,null,null,0,0],[0,0,0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,0,0,null,null,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0,null,null,0,0],[0,0,0,0,0,null,null,null,null,0,0,0,0],[0,0,0,0,0,null,null,0,0,0,0],[0,0,0,0,0,null,null,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0,null,null,0,0]]

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

  • Инициализируйте ahashMap, скажем, хм , который хранит все полное двоичное дерево.
  • Создайте функцию, скажем, allPossibleBFT с параметром N , выполнив следующие шаги:
    1. Создайте список, скажем, список , содержащий узлы класса.
    2. Если N =1 , добавьте узлы (0, NULL, NULL) в список.
    3. Теперь проверьте, является ли N нечетным, затем выполните итерацию в диапазоне [0, N-1], используя переменную x , и выполните следующие шаги:
      • Инициализируйте переменную, скажем, y как N – 1 – x .
      • Рекурсивно вызовите функцию allPossibleBFT с x в качестве параметра и назначьте ее узлу left .
        1. Рекурсивно вызовите функцию allPossibleBFT с y в качестве параметра внутри вышеприведенного вызова и назначьте его узлу right .
        2. Теперь создайте новый узел с параметрами (0, NULL, NULL).
        3. Назначьте Node.left как left и Node.right как right .
        4. Добавить узел в список.
    4. После выполнения вышеуказанных действий вставьте list в thehashMap hm .
  • После выполнения всех шагов распечатайте полные бинарные деревья, которые есть в списке.

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


Временная сложность: O(2 N )
Космическая сложность: О( 2Н )

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