Метод 1: рекурсивный поиск в глубину (DFS)
Один из самых простых подходов к подсчету конечных узлов — выполнение рекурсивного поиска в глубину (DFS) обхода двоичного дерева. Начиная с корневого узла, мы рекурсивно обходим каждый узел и увеличиваем счетчик всякий раз, когда встречаем листовой узел. Вот пример реализации на C:

unsigned int getLeafCount(struct node* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return getLeafCount(root->left) + getLeafCount(root->right);
}

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

from collections import deque
def getLeafCount(root):
    if root is None:
        return 0
    queue = deque()
    queue.append(root)
    leaf_count = 0
    while queue:
        node = queue.popleft()
        if node.left is None and node.right is None:
            leaf_count += 1
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return leaf_count

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

public int getLeafCount(TreeNode root) {
    int leafCount = 0;
    TreeNode current = root;
    while (current != null) {
        if (current.left == null) {
            if (current.right == null) {
                leafCount++;
            }
            current = current.right;
        } else {
            TreeNode predecessor = current.left;
            while (predecessor.right != null && predecessor.right != current) {
                predecessor = predecessor.right;
            }
            if (predecessor.right == null) {
                predecessor.right = current;
                current = current.left;
            } else {
                predecessor.right = null;
                if (current.right == null) {
                    leafCount++;
                }
                current = current.right;
            }
        }
    }
    return leafCount;
}

Подсчет конечных узлов в бинарном дереве — важная операция в различных алгоритмах, связанных с деревьями. В этой статье мы рассмотрели три различных метода: рекурсивный DFS, итеративный BFS с использованием очереди и обход Морриса. Каждый метод предлагает свой подход к решению проблемы. В зависимости от конкретных требований вашего приложения вы можете выбрать наиболее подходящий метод. Не забудьте проанализировать временные и пространственные сложности каждого метода, чтобы принять обоснованное решение.

Поняв эти различные подходы к подсчету конечных узлов, вы получите прочную основу для решения аналогичных проблем в будущем. Приятного кодирования!