Сверхъестественные Способности: Как Найти Путь через Бинарное Дерево, Не Потратив Ни Капли Энергии! leetcode path sum

Бинарные деревья - это важные структуры данных в компьютерных науках и программировании, предлагающие иерархический способ организации данных. Одна из распространенных задач в бинарных деревьях - определение существования пути от корня до листового узла, где сумма значений по этому пути равна заданной цели. Эта проблема, часто встречаемая в алгоритмических интервью и реальных приложениях, требует внимательного обхода и анализа структуры дерева.

Понимание проблемы

Предположим, что у нас есть корень бинарного дерева и целое число targetSum. Наша задача - определить, существует ли путь от корня до листового узла в дереве так, что сумма значений по этому пути равна targetSum. Проще говоря, нам нужно пройти по дереву от корня до листьев, отслеживая сумму значений, встреченных по пути, и проверить, удовлетворяет ли какой-либо такой путь заданному условию.

Подход и Алгоритм

Для эффективного решения этой задачи мы можем использовать рекурсивный подход поиска в глубину (DFS). Вот пошаговое объяснение нашего алгоритма:

1. Базовый случай: Если текущий узел равен null, вернуть false, указывая на то, что текущий путь не ведет к заданной сумме.
2. Проверка листового узла: Если текущий узел является листовым узлом (т.е. у него нет детей), сравните сумму текущего пути с targetSum. Если они равны, верните true, в противном случае верните false.
3. Рекурсивное исследование: Рекурсивно исследуйте левое и правое поддеревья текущего узла. Для каждого поддерева вычитайте значение текущего узла из targetSum и продолжайте исследование.
4. Возврат результата: Если какой-либо из рекурсивных вызовов вернет true, верните true вверх по стеку вызовов; в противном случае верните false.

Реализация

public boolean hasPathSum(TreeNode root, int targetSum) {
return hasPathSum(root, targetSum, 0);
}

public boolean hasPathSum(TreeNode root, int targetSum, int tempSum) {
if(root==null) return false;
tempSum += root.val;
if(tempSum == targetSum && root.left == null && root.right == null) return true;
else return hasPathSum(root.left, targetSum, tempSum) || hasPathSum(root.right, targetSum, tempSum);
}

Пример из leetCode дано дерево на рисунке и targetSum = 22:

public static void main(String[] args) {
TreeNode treeNode1 = new TreeNode(5);
TreeNode treeNode2 = new TreeNode(4);
TreeNode treeNode3 = new TreeNode(8);
TreeNode treeNode4 = new TreeNode(11);
TreeNode treeNode5 = new TreeNode(13);
TreeNode treeNode6 = new TreeNode(4);
TreeNode treeNode7 = new TreeNode(7);
TreeNode treeNode8 = new TreeNode(2);
TreeNode treeNode9 = new TreeNode(1);

treeNode1.left = treeNode2;
treeNode1.right = treeNode3;
treeNode2.left = treeNode4;
treeNode4.left = treeNode7;
treeNode4.right = treeNode8;
treeNode3.left = treeNode5;
treeNode3.right = treeNode6;
treeNode6.right = treeNode9;


PathSum pathSum = new PathSum();

System.out.println(pathSum.hasPathSum(treeNode1, 22));
System.out.println(pathSum.hasPathSum(treeNode1, 105));

}

И код самого дерева:

public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {}
public TreeNode(int val) { this.val = val; }
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}