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

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

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

Результат должен быть такой: [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);
      }
    }