⚡️ Подсчет узлов бинарного дерева
t.me/pythonlСложность: Средняя
Условие задачи: Дан корень дерева, удовлетворяющего термину "полнота", надо посчитать количество узлов в дереве.
Полным дерево считается в случае, если на каждом уровне (возможно за исключением последнего) у каждого родителя имеется пара потомков.
Необходимо разработать алгоритм с временной сложностью менее O(n).
Пример:
Ввод: root = [1,2,3,4,5,6]
Вывод: 6
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: if root is None: return 0 return 1 + self.countNodes(root.left) + self.countNodes(root.right)