Найдите родительский узел максимальных братьев и сестер продукта в заданном двоичном дереве

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

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

Примеры:

Input: Tree:
              4
           /  
         5     2
      /  
    3    1
  /  
6   12
Output: 3
Explanation: For the above tree, the maximum product for the siblings is formed for nodes 6 and 12 which are the children of node 3.

Input: Tree:
                1
             /    
          3       5
       /       /  
     6    9  4    8
Output: 3
Explanation: For the above tree, the maximum product for the siblings is formed for nodes 6 and 9 which are the children of node 5.

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

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

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


Временная сложность: O(V), где V — количество узлов в дереве.
Вспомогательное пространство: O(V).

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