MiddleКодЧастоЕщё не отвечали

Найти путь от корня к листу в бинарном дереве с заданной суммой

Дано бинарное дерево и целевая сумма. Верните узлы одного пути от корня к листу, значения которого складываются в целевую сумму, или пустой путь, если такого нет.

Требования:

Путь обязан начинаться в корне и заканчиваться в листе.
Значения могут быть отрицательными; уточните это до написания кода.

struct Node { Node* left; Node* right; int val; };

std::vector<Node*> findPath(Node* root, int target) {
    // ваш код здесь
}

Допишите реализацию.

Запускаем поиск в глубину, несущий остаток суммы и текущий путь. В каждом узле вычитаем его значение; в листе принимаем путь тогда и только тогда, когда остаток стал нулём. Рекурсируем в детей, добавляя узел перед и снимая после (бэктрекинг). Возвращаем первый принятый путь. O(n).

✗Принимать во внутреннем узле вместо требования конца в листе
✗Считать все значения положительными и отсекать отрицательные ветви
✗Забыть снять узел при бэктрекинге, протащив его в чужой путь

→Как разрешение отрицательных значений исключает раннюю отсечку?
→Как вернуть все такие пути вместо первого?

Оглавление

Задача

Верните один путь от корня к листу с заданной суммой значений; значения могут быть отрицательными.

Решение

#include <vector>

struct Node { Node* left; Node* right; int val; };

static bool dfs(Node* n, int rem, std::vector<Node*>& path) {
    if (!n) return false;
    path.push_back(n);
    rem -= n->val;
    if (!n->left && !n->right && rem == 0) return true;   // лист и сумма сошлась
    if (dfs(n->left, rem, path) || dfs(n->right, rem, path)) return true;
    path.pop_back();                                       // бэктрекинг
    return false;
}

std::vector<Node*> findPath(Node* root, int target) {
    std::vector<Node*> path;
    dfs(root, target, path);
    return path;
}

Ключевые моменты

Принимаем только в листе с нулевым остатком, не во внутреннем узле.
Отрицательные значения запрещают раннюю отсечку — обходим обе ветви.
push_back перед спуском и pop_back после — корректный бэктрекинг.

Открыть тему в роадмапе →

Оглавление

MiddleКодЧастоЕщё не отвечали

Найти путь от корня к листу в бинарном дереве с заданной суммой

Требования:

Путь обязан начинаться в корне и заканчиваться в листе.
Значения могут быть отрицательными; уточните это до написания кода.

struct Node { Node* left; Node* right; int val; };

std::vector<Node*> findPath(Node* root, int target) {
    // ваш код здесь
}

Допишите реализацию.

✗Принимать во внутреннем узле вместо требования конца в листе
✗Считать все значения положительными и отсекать отрицательные ветви
✗Забыть снять узел при бэктрекинге, протащив его в чужой путь

→Как разрешение отрицательных значений исключает раннюю отсечку?
→Как вернуть все такие пути вместо первого?

Оглавление

Задача

Верните один путь от корня к листу с заданной суммой значений; значения могут быть отрицательными.

Решение

#include <vector>

struct Node { Node* left; Node* right; int val; };

static bool dfs(Node* n, int rem, std::vector<Node*>& path) {
    if (!n) return false;
    path.push_back(n);
    rem -= n->val;
    if (!n->left && !n->right && rem == 0) return true;   // лист и сумма сошлась
    if (dfs(n->left, rem, path) || dfs(n->right, rem, path)) return true;
    path.pop_back();                                       // бэктрекинг
    return false;
}

std::vector<Node*> findPath(Node* root, int target) {
    std::vector<Node*> path;
    dfs(root, target, path);
    return path;
}

Ключевые моменты

Принимаем только в листе с нулевым остатком, не во внутреннем узле.
Отрицательные значения запрещают раннюю отсечку — обходим обе ветви.
push_back перед спуском и pop_back после — корректный бэктрекинг.

Открыть тему в роадмапе →

Оглавление