🌳 Как проверить дерево на симметричность в Python? 🐍

Для проверки симметричности дерева в Python можно использовать следующий алгоритм:

def is_symmetric(root):
    if root is None:
        return True
    
    def is_mirror(tree1, tree2):
        if tree1 is None and tree2 is None:
            return True
        if tree1 is None or tree2 is None:
            return False
        return (tree1.val == tree2.val) and is_mirror(tree1.left, tree2.right) and is_mirror(tree1.right, tree2.left)
    
    return is_mirror(root.left, root.right)
    

В этом алгоритме мы рекурсивно проверяем симметричность дерева, сравнивая значения узлов дерева и их дочерних узлов.

Вызывая функцию is_symmetric с корневым узлом дерева, мы проверяем, является ли дерево симметричным.

Надеюсь, это поможет вам проверить дерево на симметричность в Python!

Как проверить дерево на симметричность в Python

Проверка дерева на симметричность является одной из распространенных задач, которую можно решить с помощью рекурсии. В этой статье мы рассмотрим, как написать функцию на языке Python для проверки, является ли дерево симметричным.

Что такое симметричное дерево?

Симметричное дерево, также известное как зеркальное дерево, является древовидной структурой данных, в которой левая и правая части каждого узла полностью симметричны, относительно центральной оси дерева.

Рекурсивный подход

Один из способов проверить симметричность дерева - это сравнить его левое и правое поддерево. Если оба поддерева равны и симметричны, то всё дерево будет симметричным.

Для начала, давайте определим структуру узла дерева. Мы будем использовать класс Node, который будет содержать значение узла и ссылки на его левое и правое поддеревья:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Теперь давайте создадим функцию is_symmetric, принимающую корень дерева в качестве параметра:

def is_symmetric(root):
    def is_mirror(node1, node2):
        if node1 is None and node2 is None:
            return True
        if node1 is None or node2 is None:
            return False
        return (node1.value == node2.value) and \
               is_mirror(node1.left, node2.right) and \
               is_mirror(node1.right, node2.left)
    
    return is_mirror(root, root)

Внутри главной функции is_symmetric, мы определяем дополнительную вспомогательную функцию is_mirror, которая проверяет симметричность двух поддеревьев. Если оба узла равны None, то мы достигли конца пути и дерево симметрично (базовый случай рекурсии). Если только один из узлов равен None, то дерево несимметрично. Если значения узлов равны и их левые и правые поддеревья симметричны, то мы продолжаем рекурсивно проверять остальные узлы.

Давайте рассмотрим пример использования функции is_symmetric:

# Создаем симметричное дерево
root = Node(1)
root.left = Node(2)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(4)
root.right.left = Node(4)
root.right.right = Node(3)

# Проверяем дерево на симметричность
if is_symmetric(root):
    print("Дерево является симметричным")
else:
    print("Дерево не является симметричным")

В результате выполнения этого кода на экран будет выведено сообщение "Дерево является симметричным".

Заключение

В этой статье мы рассмотрели, как проверить дерево на симметричность в языке Python с помощью рекурсии. Мы использовали рекурсивный подход, сравнивая левое и правое поддерево каждого узла. Этот подход позволяет нам эффективно определить, является ли дерево симметричным.