Как вычислить сумму значений в поддеревьях?

Концепция вычисления суммы в поддеревьях

Задача состоит в том, чтобы для каждого узла бинарного дерева найти сумму всех значений в его поддереве, включая сам узел. Это классический пример применения рекурсивного обхода в глубину (DFS) с постфиксным порядком (post-order), когда сначала обрабатываются дети, а затем родитель.

Как это работает

Алгоритм рекурсивно спускается к листьям, вычисляет сумму для каждого узла, складывая значения левого и правого поддеревьев с собственным значением. Результат сохраняется или возвращается. Такой подход гарантирует, что каждый узел посчитан ровно один раз, а сложность составляет O(n), где n — количество узлов.

Пример кода на JavaScript

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function computeSubtreeSums(root) {
  if (!root) return 0;
  const leftSum = computeSubtreeSums(root.left);
  const rightSum = computeSubtreeSums(root.right);
  root.subtreeSum = leftSum + rightSum + root.val;
  return root.subtreeSum;
}

// Пример использования:
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
computeSubtreeSums(root);
console.log(root.subtreeSum); // 6
console.log(root.left.subtreeSum); // 2
console.log(root.right.subtreeSum); // 3

Применение

Этот метод используется в задачах балансировки деревьев, анализа данных (например, вычисление среднего по поддеревьям), а также в алгоритмах, где требуется агрегация информации по иерархии (файловые системы, DOM-дерево).

Вывод: Рекурсивное вычисление суммы поддеревьев — фундаментальный приём для работы с деревьями, который легко адаптируется под любые агрегирующие функции (максимум, минимум, количество узлов). Применяйте его везде, где нужно получить сводную информацию по иерархической структуре.