Сумма элементов путей начинающихся с корня бинарного дерева

Задача. Дано бинарное дерево. Нужно вычислить суммы значений элементов для каждого из путей в бинарном дереве, начинающихся с корня дерева. Результат вернуть в порядке от самого левого пути до самого правого.

Например, для такого дерева:

Результат должен быть такой: [14, 8, 10]. Тут таких три пути:

1. 1->2->4->7
2. 1->2->5
3. 1->3->6

Решение. Будем использовать in-order обход двоичного дерева. Это, по сути, упрощенный поиск в глубину. Он нам позволит обходить дерево в том порядке, который нам нужен. Смотрите мою статью про обход двоичного дерева тут: Алгоритмы обхода двоичного дерева.

Класс для вершины бинарного дерева:

public static class BinaryTree {
  int value;
  BinaryTree left;
  BinaryTree right;

  BinaryTree(int value) {
    this.value = value;
  }
}

Алгоритм решения. Модифицируем стандартный алгоритм обхода дерева:

public static void dfs(BinaryTree tree) {
  if (tree == null) {
    return;
  }
  visit(tree);
  dfs(tree.left);
  dfs(tree.right);
}

Для того, чтобы вычилять сумму элементов при обходе бинарного дерева, будем перевадать текущую вычесленную сумму в качестве параметра функции, а также к переданной сумме добавлять значения текущей вершины:

public static void dfs(BinaryTree tree, int sum) {
  if (tree == null) {
    return;
  }
  sum += tree.value;
  visit(tree);
  dfs(tree.left, sum);
  dfs(tree.right, sum);
}

Более того, нам нужно где-то сохранять сумму всей ветки, когда мы достигли листовой вершины дерева (нет дочерних элементов). Будем хранить результат в списке и будем его также передавать в качестве параметра:

public static void dfs(BinaryTree tree, int sum, List<Integer> result) {
  sum += tree.value;
  if (tree.left == null && tree.right == null) {
    result.add(sum)
    return;
  }
  if (tree.left != null) dfs(tree.left, sum, result);
  if (tree.right != null) dfs(tree.right, sum, result);
}

На картинке я отобразил значения суммы, которое передается при вызове функции для каждой вершины:

Финальный код решения:

public static List<Integer> branchSums(BinaryTree root) {
  List<Integer> result = new ArrayList<>();
  if (root == null) {
    return result;
  }
  dfs(root, 0, result);
  return result;
}

private static void dfs(BinaryTree node, int sum, List<Integer> result) {
  //Вычисляем сумму текущего пути
  sum += node.value;
  //Если это листовая вершина дерева (нет дочерних вершин), 
  //то мы вычислили сумму для текущей ветки
  if (node.left == null && node.right == null) {
    result.add(sum);
    return;
  }
  //рекурсивно вызываем для левого и правого ребенка
  if (node.left != null) {
    dfs(node.left, sum, result);
  }
  if (node.right != null) {
    dfs(node.right, sum, result);
  }
}