Количество узлов со средним значением левого поддерева не менее K в заданном двоичном дереве.

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

Примеры:

Input :  K=5
Tree:    
               2
           /    
        5        4
      /       /  
   5   6    6   2
          /
    5    4
Output: 3
Explanation:  
               2         ——– level 0
           /                            
        5        4       ——– level 1
      /       /                      
   5   6      6   2     ——– level 2
            /                          
    5      4            ——– level 3

Left left subtree average for root node 2 = (5+5+5) / 3 = 5
Left left subtree average for node 4 at level 1 = (6+4) / 2 = 5
Left left subtree average for node 5 at level 1 = (5+5) / 2 = 5
So, these 3 nodes satisfy the given conditions.

Input: K = 4,  
Tree:           1
                /
              2
            /
          3
        /
      4
Output: 1

Подход: выполните следующие шаги, чтобы решить эту проблему:

1. Создайте глобальную переменную an для хранения ответа и инициализируйте ее значением 0 .
2. Создайте функцию countHelper , которая будет принимать узел дерева и целое число K в качестве параметра и будет возвращать пару суммы узлов и количества узлов в поддереве этого узла.
3. Теперь передайте корневой узел и K в начальном вызове этой функции.
4. При каждом вызове этой рекурсивной функции:
   1. Проверьте, является ли текущий узел листовым узлом или нет. Если это конечный узел, просто верните {0, 0} , так как сумма и количество узлов ниже этого узла равны 0 .
   2. Теперь вызовите левое и правое поддеревья.
   3. Проверьте, если для текущего узла (сумма левого и правого поддеревьев/количество узлов в левом и правом поддеревьях)>=K , если оно увеличивается на 1 .
5. После завершения рекурсивной функции выведите an .

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

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