Большинство задач на деревья укладывается в один из двух рекурсивных шаблонов. В обоих есть базовый случай (пустой узел), рекурсия по детям и объединение результата. Терминология и обходы разобраны в теме Деревья: терминология и обходы, деревья поиска — в теме BST: вставка и поиск.

Два шаблона: слева высоты поднимаются вверх, справа остаток суммы спускается вниз
Два шаблона: слева высоты поднимаются вверх, справа остаток суммы спускается вниз

Два шаблона

  1. Вернуть значение (снизу вверх). Функция возвращает ответ для поддерева, а ответ родителя собирается из ответов детей: глубина равна 1 + max(left, right).
  2. Накапливать (сверху вниз). Состояние идёт вниз параметром (остаток суммы, границы BST, текущая глубина) или собирается во внешний список (все пути, уровни).

В примерах ниже маленький помощник build строит дерево из списка по уровням, где None значит «нет узла».

Максимальная глубина и число узлов (вернуть)

python
from collections import deque

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

def build(values):
    """Level-order list, None means no node: [3, 9, 20, None, None, 15, 7]."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = Node(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i])
            queue.append(node.right)
        i += 1
    return root

def max_depth(node):
    if node is None:
        return 0                                  # base case
    return 1 + max(max_depth(node.left), max_depth(node.right))

def count(node):
    return 0 if node is None else 1 + count(node.left) + count(node.right)

tree = build([3, 9, 20, None, None, 15, 7])
print("depth:", max_depth(tree), "nodes:", count(tree))
text
depth: 3 nodes: 5

Сумма пути и все пути (накапливать)

has_path_sum передаёт остаток суммы вниз и проверяет его в листе. all_paths накапливает текущий путь: добавить, рекурсия, отменить. Это та же идея «выбрать, исследовать, отменить», что и в переборе с возвратом.

python
from collections import deque

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

def build(values):
    """Level-order list, None means no node: [3, 9, 20, None, None, 15, 7]."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = Node(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i])
            queue.append(node.right)
        i += 1
    return root