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

Метод 1: рекурсивный подход
Один из способов идентифицировать униальные деревья — использовать рекурсивный подход. Мы можем начать с корневого узла и пройти по дереву, проверяя, соответствует ли значение каждого узла значению его родительского узла. Если это так, мы продолжаем рекурсивно спускаться по дереву. Вот пример фрагмента кода на Python:

def is_unival_recursive(node):
    if node is None:
        return True
    if node.left is not None and node.left.value != node.value:
        return False
    if node.right is not None and node.right.value != node.value:
        return False
    return is_unival_recursive(node.left) and is_unival_recursive(node.right)

Метод 2: итеративный подход
Другой подход заключается в использовании итеративного метода, например поиска в ширину (BFS) или поиска в глубину (DFS). Мы можем перемещаться по дереву и отслеживать встречающиеся уникальные значения. Если мы найдем более одного уникального значения, это означает, что дерево не является универсальным. Вот пример использования подхода DFS:

def is_unival_iterative(node):
    if node is None:
        return True
    stack = [node]
    value = node.value
    while stack:
        current = stack.pop()
        if current.value != value:
            return False
        if current.left is not None:
            stack.append(current.left)
        if current.right is not None:
            stack.append(current.right)
    return True

Метод 3: подсчет универсальных деревьев
Теперь, когда мы знаем, как идентифицировать универсальное дерево, давайте поговорим о их подсчете в данном двоичном дереве. Мы можем немного изменить наш рекурсивный подход, чтобы отслеживать подсчет. Вот пример фрагмента кода:

def count_unival_trees(root):
    count = [0]  # Using a mutable reference to update the count
    def helper(node):
        if node is None:
            return True
        left = helper(node.left)
        right = helper(node.right)
        if left and right and (node.left is None or node.left.value == node.value) and (node.right is None or node.right.value == node.value):
            count[0] += 1
            return True
        return False
    helper(root)
    return count[0]

Универсальные деревья — это интересные структуры данных, которые можно найти в двоичных деревьях. Мы рассмотрели три метода идентификации и подсчета универсальных деревьев в вашем коде: рекурсивный подход, итеративный подход и подсчет универсальных деревьев. Вооружившись этими методами, вы теперь можете легко использовать универсальные деревья в своих приключениях по программированию. Удачного программирования, и пусть универсальные деревья всегда будут на вашей стороне!