112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example, given the below binary tree and sum = 22:

return true, as there exist a root-to-leaf path 5 → 4 → 11 → 2 which sum is 22.

112. Сумма на пути

Задано бинарное дерево и сумма. Существует ли путь от корня до листа, сумма чисел на котором равна в точности заданной сумме.

Рассмотрим бинарное дерево с суммой sum = 22:

вернет true, так как существует путь от корня до листа 5 → 4 → 11 → 2 с суммой 22.

class Solution {

public:

bool hasPathSum(TreeNode *root, int sum) {

}

};

РЕШЕНИЕ

структуры данных - деревья

Анализ алгоритма

Реализуем поиск в глубину на дереве. Будем подсчитывать сумму чисел на пути от корня до каждой вершины. Когда дойдем до листа (вершина у которой левый и правый сыновья равны NULL), сравним накопленную сумму sum с заданной target.

Реализация алгоритма

class Solution

{

public:

bool hasPathSum(TreeNode *root, int sum)

{

if(root == NULL) return false;

return DFS(sum, 0, root);

}

bool DFS(int target, int sum, TreeNode* root)

{

if(root == NULL)

return false;

sum += root->val;

if(root->left == NULL && root->right == NULL)

{

if(sum == target)

return true;

else

return false;

}

bool leftPart = DFS(target, sum, root->left);

bool rightPart = DFS(target, sum, root->right);

return leftPart || rightPart;

}

};