Подсчитайте узлы с суммой путей, сделанных только левыми дочерними узлами не менее K
Для заданного бинарного дерева и целого числа K задача состоит в том, чтобы написать программу для подсчета количества узлов, так что путь от текущего узла до листа, состоящего только из левого дочернего узла узлов, имеет сумму, большую или равную K .
Примеры:
Input: K = 15,
Tree:
8
/
9 10
/ /
11 12 13 7
/ / / /
6 9 6 7 15 11Output: 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 = 15Input: K = 20,
Tree:
3
/
16 10Output: 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) пространство, используемое стеком рекурсии.