Сумма элементов путей начинающихся с корня бинарного дерева
Published: 2023-11-25 22:17:54


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

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

![](https://cdn-images-1.medium.com/max/2000/1*NdgtveQnb33OBwWYsOKFOw.png)

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

 1. 1->2->4->7

 2. 1->2->5

 3. 1->3->6

![](https://cdn-images-1.medium.com/max/2000/1*fWTCrRwz0JoOt9QbVZXMAQ.png)

**Решение**. Будем использовать **in-order обход двоичного дерева**. Это, по сути, упрощенный поиск в глубину. Он нам позволит обходить дерево в том порядке, который нам нужен. Смотрите мою статью про обход двоичного дерева тут: [Алгоритмы обхода двоичного дерева](https://dev.to/faangmaster/alghoritmy-obkhoda-dvoichnogho-dierieva-26l4).

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

```java
    public static class BinaryTree {
      int value;
      BinaryTree left;
      BinaryTree right;
    
      BinaryTree(int value) {
        this.value = value;
      }
    }
```

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

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

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

```java
    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);
    }
```

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

```java
    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);
    }
```

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

![](https://cdn-images-1.medium.com/max/2060/1*MftwcLRKxX7HQn8vNR1Qag.png)

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

```java
    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);
      }
    }
```