Измените двоичное дерево, заменив каждый узел произведением всех оставшихся узлов.

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

Примеры:

Input:
          1
      /    
   2        3
          /    
        4      5
Output:
      120
      /  
  60   40
         /  
     30   24          

Input:
         2
      /  
  2       3
Output:
      6
   /  
6      4

Подход: Данную проблему можно решить, сначала вычислив произведение всех узлов в заданном дереве, а затем выполнив любой обход дерева в заданном дереве и обновив каждый узел значением (P/(root->values) . Следуйте шаги ниже, чтобы решить проблему:

• Найдите произведение всех узлов бинарного дерева с помощью Preorder Traversa и сохраните его в переменной, скажем, P .
• Определите функцию, скажем, updateTree(root, P) и выполните следующие шаги:
  • Если значение root равно NULL , то возврат из функции.
  • Обновите текущее значение корневого узла до значения (P/root->value) .
  • Рекурсивно вызывать левое и правое поддеревья как updateTree(root->left, P) и updateTree(root->right, P) .
• После выполнения вышеуказанных шагов распечатайте Inorder Traversalизмененного дерева.

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

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