Задача. Дано бинарное дерево. Нужно вычислить суммы значений элементов для каждого из путей в бинарном дереве, начинающихся с корня дерева. Результат вернуть в порядке от самого левого пути до самого правого.
Например, для такого дерева:
Результат должен быть такой: [14, 8, 10]. Тут таких три пути:
1->2->4->7
1->2->5
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);
}
}
Top comments (0)