Паттерн "снизу вверх"

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

Любая задача на этот паттерн сводится к двум вопросам:

Что вернуть для пустого узла?
Что вернуть родителю, зная ответы левого и правого поддерева?

def solve(node):
    if node is None:
        return ...                # базовый случай

    left  = solve(node.left)      # ответ от левого поддерева
    right = solve(node.right)     # ответ от правого поддерева

    return ...                    # формируем ответ и возвращаем родителю

Разбор задачи

Дан корень бинарного дерева. Нужно посчитать количество узлов в дереве.

Каждый узел спрашивает у левого и правого поддерева «сколько у вас узлов?», складывает ответы и прибавляет 1 (себя). Для пустого узла возвращаем 0.

public class Solution
{
    public static int CountNodes(TreeNode node)
    {
        if (node == null)
        {
            return 0;
        }

        int left = CountNodes(node.left);
        int right = CountNodes(node.right);

        return left + right + 1;
    }
}

using namespace std;

int countNodes(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }

    int left = countNodes(node->left);
    int right = countNodes(node->right);

    return left + right + 1;
}

package main

func countNodes(node *TreeNode) int {
    if node == nil {
        return 0
    }

    left := countNodes(node.left)
    right := countNodes(node.right)

    return left + right + 1
}

public class Solution {

    public int countNodes(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = countNodes(node.left);
        int right = countNodes(node.right);

        return left + right + 1;
    }
}

from typing import *


def count_nodes(node: Optional[TreeNode]) -> int:
    if node is None:
        return 0

    left = count_nodes(node.left)
    right = count_nodes(node.right)

    return left + right + 1

/**
 * @param {TreeNode} node
 * @returns {number}
 */
export function countNodes(node) {
  if (node === null) {
    return 0;
  }

  const left = countNodes(node.left);
  const right = countNodes(node.right);

  return left + right + 1;
}

Оценка сложности

Время: O(n), где n — число вершин в дереве, потому что заходим в каждый узел один раз
Память: O(h), где h — высота дерева, память тратится на стек рекурсивных вызовов

Типичные ошибки

Лишние проверки детей. Проверять node.left is None and node.right is None вместо node is None — так пропускаются краевые случаи и ловятся исключения на пустых узлах.
Нет проверки на пустой узел. Первая строчка функции — всегда if node is None. Без неё рекурсия упадёт при обращении к несуществующему узлу.

Маркер паттерна "снизу вверх": нужно собирать ответ от листьев к корню и ответ в каждом узле зависит от ответов детей.