Задача.
Дано бинарное дерево поиска. Нужно найти сумму всех вершин этого дерева, значения которых лежит в диапазоне значений от low до high включительно.
Например, для дерева
Сумма элементов в диапазоне от 7 до 15, равна 10 + 7 + 15 = 32
Решение.
Бинарное или Двоичное Дерево Поиска это двоичное дерево, у которого значения во всех вершинах левого поддерева меньше или равны значению в самой вершине, а значения во всех вершинах правого поддерева строго больше значения в самой вершине. Более того, левое и правое поддерево являются двоичными деревьями поиска. Т.е. это свойство выполняется рекурсивно. Свойства для значений вершин соблюдается для всех поддеревьев.
Класс вершины двоичного дерева:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
По сути, нам нужно просто обойти дерево и просуммировать все элементы, значения которых лежат в заданных пределах.
Для обхода дерева воспользуемся pre-order алгоритмом обхода двоичного дерева.
public static void dfs(BinaryTree tree) {
if (tree == null) {
return;
}
visit(tree);
dfs(tree.left);
dfs(tree.right);
}
Вместо visit нам нужно добавить логику на проверку того, что значение лежит в нужном диапазоне и добавить значение к сумме:
//Если значение в заданном диапазоне, то добавляем его к сумме
if (root.val >= low && root.val <= high) {
sum += root.val;
}
Т.к. у нас в условии дано Двоичное Дерево Поиска, то мы можем сократить число рекурсивных вызовов для поддеревьев.
Например, для дерева из примера, если мы находимся в вершине 5, то делать рекурсивный вызов для левого поддерева не имеет смысл, т.к. там по определению Бинарного Дерева Поиска все значения меньше или равны 5. А у нас диапазон от 7 до 15. Т.е. искать в левом поддереве не имеет смысла, если значение в вершине меньше нижней границы заданного диапазона.
Аналогично для правого поддерева, там искать нет смысла, если значение в вершине больше верхнего предела заданного диапазона. Т.к. по определению Бинарного Дерева Поиска там все значения больше, чем в текущей вершине, а значит лежат за пределами нашего диапазона.
Тогда финальное решение выглядит так:
public int rangeSumBST(TreeNode root, int low, int high) {
//base-case
if (root == null) {
return 0;
}
int sum = 0;
//Если значение в заданном диапазоне, то добавляем его к сумме
if (root.val >= low && root.val <= high) {
sum += root.val;
}
//В левое поддерево имеет смысл идти только, когда нижняя
//граница меньше значения в текущей вершине
if (low < root.val) {
sum += rangeSumBST(root.left, low, high);
}
//В правое поддерево имеет смысл идти только, когда верхняя
//граница больше значения в текущей вершине
if (high > root.val) {
sum += rangeSumBST(root.right, low, high);
}
return sum;
}
Top comments (0)