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

Опубликовано: 26 Февраля, 2023

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

Примеры:

Input: K = 15, 
Tree: 
                       8
                 /          
              9             10
         /               /    
     11      12    13    7
   /        /        /      /  
 6    9   6      7     15   11

Output: 4
Explanation: Nodes with left children sum ≥ ‘K’ are :
Node 8 = 9 + 11 + 6 = 26
Node 9 = 11 + 6 = 17
Node 10 = 13 + 7 = 20
Node 7 = 15

Input:  K = 20,  
Tree: 
                   3
              /      
          16     10 

Output: 0
Explanation: No nodes with left children sum ≥ 20

Подход: Чтобы решить проблему, следуйте следующей идее:

One simple approach is to find the sum of left children nodes for every node and compare it with K.

Следуйте инструкциям, чтобы решить проблему:

  • Ведение счетчика с количеством имен
  • Реализуйте рекурсивную функцию leftNodeSum , которая рекурсивно вычисляет сумму левых узлов для каждого узла в дереве.
  • Используйте рекурсивную функцию для обхода каждого узла
  • Проверьте сумму с помощью K , если она больше K , увеличьте значение count .
  • Верните количество в качестве ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N^2)
Вспомогательное пространство: O(N) пространство, используемое стеком рекурсии.

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